B. Еще одна задача о монетах
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$5$$$ различных типов монет, каждый из которых имеет значение равное одному из первых $$$5$$$ треугольных чисел: $$$1$$$, $$$3$$$, $$$6$$$, $$$10$$$ и $$$15$$$. Все типы монет имеются в неограниченном количестве. Ваша задача — определить, какого минимального количества монет достаточно, чтобы набрать сумму ровно $$$n$$$.

Можно показать, что ответ всегда существует.

Входные данные

В первой строке находится одно целое число $$$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
Примечание

В первом наборе тестовых данных, где $$$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$$$.