该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你有 5 种不同的硬币，每种硬币的价值都等于前 5 个三角形数字中的一个： 1 、 3 、 6 、 10 和 15 。这些硬币种类非常多。你的目标是找出所需的最少数量的这些硬币，使它们的总价值相加正好是 𝑛 。

我们可以证明答案总是存在的。

输入

第一行包含一个整数 $t$ ($1 \le t \le 10^4$) - 测试用例的数量。测试用例说明如下。

每个测试用例的第一行包含一个整数 $n$ ($1 \leq n \leq 10^9$) - 目标值。

输出

对于每个测试用例，输出一个数字，即所需硬币的最少数量。

样例

14
1
2
3
5
7
11
12
14
16
17
18
20
98
402931328

1
2
1
3
2
2
2
3
2
3
2
2
8
26862090

**注**

在第一个测试案例中，对于 𝑛=1 ，答案是 1 ，因为只需一枚 1 值的硬币即可。 1=1⋅1 .

在第四个测试案例中，对于 n=5 ，答案是 3 ，可以使用两个 1 面值的硬币和一个 3 面值的硬币。 5=2⋅1+1⋅3 .

在第七个测试案例中，对于 𝑛=12 ，答案是 2 ，可以使用两个 6 值的硬币来实现。

在第九个测试情形中，对于 𝑛=16 ，答案是 2 ，可以使用一枚 1 面值的硬币和一枚15 面值的硬币，或者使用一枚 10 面值的硬币和一枚 6 面值的硬币。 16=1⋅1+1⋅15=1⋅6+1⋅10 .

Limitation

1s, 1024KiB for each test case.