311101: CF1934B. Yet Another Coin Problem

B. Yet Another Coin Problemtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You have $5$ different types of coins, each with a value equal to one of the first $5$ triangular numbers: $1$, $3$, $6$, $10$, and $15$. These coin types are available in abundance. Your goal is to find the minimum number of these coins required such that their total value sums up to exactly $n$.

We can show that the answer always exists.

Input

The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 10^9$) — the target value.

Output

For each test case, output a single number — the minimum number of coins required.

ExampleInput

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

Output

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

Note

In the first test case, for $n = 1$, the answer is $1$ since only one $1$ value coin is sufficient. $1 = 1 \cdot 1$.

In the fourth test case, for $n = 5$, the answer is $3$, which can be achieved using two $1$ value coins and one $3$ value coin. $5 = 2 \cdot 1 + 1 \cdot 3$.

In the seventh test case, for $n = 12$, the answer is $2$, which can be achieved using two $6$ value coins.

In the ninth test case, for $n = 16$, the answer is $2$, which can be achieved using one $1$ value coin and one $15$ value coin or using one $10$ value coin and one $6$ value coin. $16 = 1 \cdot 1 + 1 \cdot 15 = 1 \cdot 6 + 1 \cdot 10$.

题目大意：
你有5种不同面值的硬币，每种硬币的面值等于前5个三角形数：1, 3, 6, 10, 和 15。这些硬币的数量是充足的。你的目标是找到最少的硬币数量，使得它们的总价值恰好为n。

输入数据格式：
第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试用例的数量。接下来是t个测试用例的描述。
每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 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
```

注意：
- 在第一个测试用例中，n = 1，答案为1，因为只需要一个面值为1的硬币。1 = 1 × 1。
- 在第四个测试用例中，n = 5，答案为3，可以使用两个面值为1的硬币和一个面值为3的硬币。5 = 2 × 1 + 1 × 3。
- 在第七个测试用例中，n = 12，答案为2，可以使用两个面值为6的硬币。
- 在第九个测试用例中，n = 16，答案为2，可以使用一个面值为1的硬币和一个面值为15的硬币，或者使用一个面值为6的硬币和一个面值为10的硬币。16 = 1 × 1 + 1 × 15 = 1 × 6 + 1 × 10。题目大意： 你有5种不同面值的硬币，每种硬币的面值等于前5个三角形数：1, 3, 6, 10, 和 15。这些硬币的数量是充足的。你的目标是找到最少的硬币数量，使得它们的总价值恰好为n。 输入数据格式： 第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试用例的数量。接下来是t个测试用例的描述。 每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 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 ``` 注意： - 在第一个测试用例中，n = 1，答案为1，因为只需要一个面值为1的硬币。1 = 1 × 1。 - 在第四个测试用例中，n = 5，答案为3，可以使用两个面值为1的硬币和一个面值为3的硬币。5 = 2 × 1 + 1 × 3。 - 在第七个测试用例中，n = 12，答案为2，可以使用两个面值为6的硬币。 - 在第九个测试用例中，n = 16，答案为2，可以使用一个面值为1的硬币和一个面值为15的硬币，或者使用一个面值为6的硬币和一个面值为10的硬币。16 = 1 × 1 + 1 × 15 = 1 × 6 + 1 × 10。