题目描述

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

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

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

输入格式

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

对于每组测试数据，输入一行一个整数 $x$，表示 XRH 的存款数，单位为元。

输出格式

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

样例

1
100

1

数据范围与提示

• $1 \le t \le 100$
• $1 \le x \le 10000$