CF1934B.Yet Another Coin Problem

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.

你有 $5$ 种不同类型的硬币，其面值分别为前 $5$ 个三角形数：$1$、$3$、$6$、$10$ 和 $15$。这些类型的硬币数量充足。你的目标是找出所需硬币的最少数量，使得它们的总面值恰好等于 $n$。

可以证明，该问题的答案总是存在。

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.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。随后是各测试用例的描述。

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

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

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

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$.

在第一个测试用例中，当 $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$。