1336:地精商人

时间限制: 1 S | 内存限制: 8192 KB
Accept: 0 | Submit: 0
[提交] [状态] [讨论版]
描述

你是一个地精商人,本地人经常向你购买商品。由于未实现支付宝或者微信支付业务,人们买东西时会携带一堆各种面值的金币,每枚金币的面额都是10的非负整数次幂(1、10、100、...),你也可以找钱(金币)给他们,如果他们付钱超过了应付金额,同样的,找钱的金币也是10的非负整数次幂。

由于你存放金币的地方离店铺很远,而且金币很重,你希望收钱和找钱用到的金币数量之和尽可能的少(因为不同面额金币的重量是一样的)。假设顾客携带了足够数量各种面值的金币,你可以要求客户给你哪几种面值的金币各几个。

已知你出售的商品价格,问收钱和找钱用到的金币数量之和最少是多少?

输入

一个正整数n,表示案例的数量。(n<=20)

每组案例由一个非常大的正整数m组成,表示商品的价格。(m<=10的1000次方)

输出

针对每组案例,输出一个整数,表示收钱和找钱用到的金币数量之和最少是多少。

每组案例输出完都要换行。

样例输入

3

13

83

12345678987654321

样例输出

4

6

42

HINT

第一组案例中,商品价格13,最佳方案是客户支付1个10,3个1,一共涉及4个金币。

第二组案例中,商品价格83,最佳方案是客户支付1个100,3个1,找回2个10,一共涉及6个金币。

来源
19-20(2)第3次线上赛