CF1934B Yet Another Coin Problem

你有 $5$ 种不同面值的硬币，每种硬币的面值分别为前 $5$ 个三角数：$1$、$3$、$6$、$10$ 和 $15$。这些硬币的数量都足够多。你的目标是找到最少需要多少枚这些硬币，使它们的总面值恰好等于 $n$。 可以证明答案总是存在。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 10^9$），表示目标面值。

对于每个测试用例，输出一个整数，表示所需的最少硬币数。

在第一个测试用例中，对于 $n = 1$，答案是 $1$，因为只需要一枚面值为 $1$ 的硬币。$1 = 1 \times 1$。 在第四个测试用例中，对于 $n = 5$，答案是 $3$，可以用两枚面值为 $1$ 的硬币和一枚面值为 $3$ 的硬币。$5 = 2 \times 1 + 1 \times 3$。 在第七个测试用例中，对于 $n = 12$，答案是 $2$，可以用两枚面值为 $6$ 的硬币。 在第九个测试用例中，对于 $n = 16$，答案是 $2$，可以用一枚面值为 $1$ 的硬币和一枚面值为 $15$ 的硬币，或者用一枚面值为 $10$ 的硬币和一枚面值为 $6$ 的硬币。$16 = 1 \times 1 + 1 \times 15 = 1 \times 6 + 1 \times 10$。 由 ChatGPT 4.1 翻译