Условие

На автоматизированном складе используются жетоны пяти номиналов: 1, 3, 6, 10 и 15.

Для каждой заявки нужно выдать ровно n единиц товара, используя некоторое количество жетонов. Один жетон можно использовать неограниченное число раз.

Ваша задача — для каждой заявки определить минимальное количество жетонов, с помощью которых можно набрать сумму n.

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

В первой строке дано целое число t — количество заявок.

В каждой из следующих t строк дано одно целое число n — требуемая сумма.

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

Для каждой заявки выведите одно целое число — минимальное количество жетонов, необходимое для набора суммы n.

Ограничения

• 1 <= t <= 10^4
• 1 <= n <= 10^9

Пример 1

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

4
1
3
20
23

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

1
1
2
3

Пояснение

• Для n = 1 достаточно одного жетона 1.
• Для n = 3 достаточно одного жетона 3.
• Для n = 20 можно взять жетоны 10 + 10, всего 2 жетона.
• Для n = 23 можно взять жетоны 10 + 10 + 3, всего 3 жетона.

Примечание

Обратите внимание: использовать как можно больше жетонов номинала 15 не всегда оптимально. Например, для суммы 20 лучше взять два жетона по 10, чем один жетон 15 и добирать остаток более мелкими.