月球货币置换

题目描述

由于月球上不流通RMB，XRH 准备将自己的 N 元钱全部换成月球上的硬通货，一分钱也不留给 DT 的小弟们。

月球上流通的物品及其价格如下：

时间紧迫，XRH 需要以最少的物品数量完成置换，且不能有剩余零钱。请计算他最少需要置换多少个物品。

输入格式

第一行一个整数 t，表示测试数据的组数。

对于每组测试数据：

• 一行一个整数 x，表示 XRH 的存款数（单位：元）。

输出格式

对于每组测试数据，输出一行一个整数，表示 XRH 最少需要置换的物品数量。

样例输入

2
1234
6

样例输出

18
2

样例说明

• 第一组样例（1234元）：

  • 先换12个🐑手办（12×100=1200元）
  • 再换1个皮卡丘鼠标垫（20元）和1听氧乐多（10元）
  • 最后换4瓶地球无用的空气（4×1=4元）
  • 总物品数：12+1+1+4=18个。

• 第二组样例（6元）：

  • 换1张XRH珍藏的17私房照（5元）
  • 换1瓶地球无用的空气（1元）
  • 总物品数：1+1=2个。

数据范围

• 对于 100% 的数据，1 ≤ t ≤ 100，0 ≤ x ≤ 10^9。