| Codeforces Round 639 (Div. 2) |
|---|
| Закончено |
Карточная пирамида высоты $$$1$$$ может быть построена с помощью двух карт, приставленных друг к другу. Для $$$h>1$$$ карточная пирамида высоты $$$h$$$ может быть построена расположением карточной пирамиды высоты $$$h-1$$$ на базе. База состоит из $$$h$$$ пирамидок высоты $$$1$$$, поставленных в ряд, и $$$h-1$$$ карты, лежащей сверху на них. Например, карточные пирамиды с высотами $$$1$$$, $$$2$$$ и $$$3$$$ выглядят следующим образом:
Изначально у вас есть $$$n$$$ карт и вы строите как можно более высокую пирамиду из этих карт. Если остались лишние карты, вы снова строите как можно более высокую пирамиду из оставшихся карт. Вы продолжаете этот процесс до тих пор, пока не станет невозможно построить какую-нибудь пирамиду. Сколько карточных пирамид вы построите?
Каждый тест состоит из нескольких тестовых случаев. Первая строка содержит единственное целое число $$$t$$$ ($$$1\le t\le 1000$$$) — количество тестовых случаев. Следующие $$$t$$$ строк содержат описания тестовых случаев.
Единственная строка описания каждого тестового случая содержит единственное целое число $$$n$$$ ($$$1\le n\le 10^9$$$) — количество карт.
Гарантируется, что сумма значений $$$n$$$ по всем тестовым случаям не превосходит $$$10^9$$$.
Для каждого тестового случая выведите единственное целое число — количество карточных пирамид, которое вы построите в конце процесса.
5 3 14 15 24 1
1 2 1 3 0
В первом тестовом случае вы построите карточную пирамиду высоты $$$1$$$ из $$$2$$$-x карт. Останется $$$1$$$ карта, которой недостаточно, чтобы построить какую-нибудь пирамиду.
Во втором тестовом случае вы построите две пирамиды, каждая высоты $$$2$$$, и в конце процесса не останется карт.
В третьем тестовом случае вы построите одну пирамиду высоты $$$3$$$, и ни одной карты не останется.
В четвертом тестовом случае вы сначала построите одну пирамиду высоты $$$3$$$, и $$$9$$$ карт останется. Затем вы построите пирамиду высоты $$$2$$$, и $$$2$$$ карты останется. Наконец, вы построите последнюю пирамиду высоты $$$1$$$, и не останется ни одной карты.
В пятом тестовом случае одной карты недостаточно, чтобы построить какую-нибудь пирамиду.
