题目描述

因为在月球RMB不是流通的，所以 XRH 准备提前准备将自己的 N 元钱换成月球上的硬通货，不给 DT 的小弟们留一分钱。

流通物品价格如下：

因为时间紧任务重，XRH 需要尽量少的置换物品并且没有剩余零钱，请问他最少置换多少物品。

输入说明

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

对于每组测试数据：

一行一个整数 x 表示存款数

输出说明

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

Input

2
1234
6

Output

18 
2

样例说明

• 第一组样例
  1. 先换 4 瓶空气
  2. 再换一个 PKQ 鼠标垫和一听氧乐多
  3. 再换 12 个 🐑手办
  4. 一共置换18个物品
• 第二组样例
  • 打印一张 XRH私藏的17私房照
  • 换一瓶地球的空气
  • 一共置换两个物品

数据范围

• 对于 100% 的数据， $1~\leq~t~\leq100,~0~\leq~x~\leq~10^9$