您有 $$$5$$$ 不同类型的硬币,每种硬币的价值等于前 $$$5$$$ 三角形数字之一:$$$1$$$、$$$3$$$、$$$6$$$、$$$10$$$ 和 $$$15$$$。这些硬币类型非常丰富。您的目标是找到所需的最少数量的硬币,使其总价值恰好为 $$$n$$$。
我们可以证明答案总是存在的。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^9$$$) — 目标值。
输出
对于每个测试用例,输出一个数字 - 所需的最小硬币数量。
示例
输入 #1
14 1 2 3 5 7 11 12 14 16 17 18 20 98 402931328
输出 #1
1 2 1 3 2 2 2 3 2 3 2 2 8 26862090
注意
在第一个测试用例中,对于 $$$n = 1$$$,答案是 $$$1$$$,因为只有一枚 $$$1$$$ 价值的硬币就足够了。 $$$1 = 1 \cdot 1$$$。
在第四个测试用例中,对于$$$n = 5$$$,答案是$$$3$$$,这可以使用两个$$$1$$$价值硬币和一个$$$3$$$价值硬币来实现。 $$$5 = 2 \cdot 1 + 1 \cdot 3$$$。
在第七个测试用例中,对于$$$n = 12$$$,答案是$$$2$$$,这可以使用两个$$$6$$$价值的硬币来实现。
在第九个测试用例中,对于$$$n = 16$$$,答案是$$$2$$$,这可以使用一枚$$$1$$$价值硬币和一枚$$$15$$$价值硬币或使用一枚$$$10$$$价值硬币和一枚$$$6$$$价值硬币来实现。 $$$16 = 1 \cdot 1 + 1 \cdot 15 = 1 \cdot 6 + 1 \cdot 10$$$。