Карточные пирамиды

Помогите решить задачу:
Карточная пирамида высоты 1 может быть построена с помощью двух карт, приставленных друг к другу. Для h>1 карточная пирамида высоты h может быть построена расположением карточной пирамиды высоты h−1 на базе. База состоит из h пирамидок высоты 1, поставленных в ряд, и h−1 карты, лежащей сверху на них. Например, карточные пирамиды с высотами 1, 2 и 3 выглядят следующим образом:


Изначально у вас есть n карт и вы строите как можно более высокую пирамиду из этих карт. Если остались лишние карты, вы снова строите как можно более высокую пирамиду из оставшихся карт. Вы продолжаете этот процесс до тих пор, пока не станет невозможно построить какую-нибудь пирамиду. Сколько карточных пирамид вы построите?

Входные данные
Каждый тест состоит из нескольких тестовых случаев. Первая строка содержит единственное целое число t (1≤t≤1000) — количество тестовых случаев. Следующие t строк содержат описания тестовых случаев.

Единственная строка описания каждого тестового случая содержит единственное целое число n (1≤n≤109) — количество карт.

Гарантируется, что сумма значений n по всем тестовым случаям не превосходит 109.

Выходные данные
Для каждого тестового случая выведите единственное целое число — количество карточных пирамид, которое вы построите в конце процесса.

Пример
входные данные
5
3
14
15
24
1
выходные данные
1
2
1
3
0
Примечание
В первом тестовом случае вы построите карточную пирамиду высоты 1 из 2-x карт. Останется 1 карта, которой недостаточно, чтобы построить какую-нибудь пирамиду.

Во втором тестовом случае вы построите две пирамиды, каждая высоты 2, и в конце процесса не останется карт.

В третьем тестовом случае вы построите одну пирамиду высоты 3, и ни одной карты не останется.

В четвертом тестовом случае вы сначала построите одну пирамиду высоты 3, и 9 карт останется. Затем вы построите пирамиду высоты 2, и 2 карты останется. Наконец, вы построите последнюю пирамиду высоты 1, и не останется ни одной карты.

В пятом тестовом случае одной карты недостаточно, чтобы построить какую-нибудь пирамиду.

0

Расскажу тебе сказку про карточный домик. Очевидно, что каждый следующий этаж - это количество карт с прошлого этажа + 3 * n - 1.
Т.е. можно посчитать так: c = 3 * (1 + 2 + ... + n) - n = 3 * (n * (n + 1) / 2) - n = n * (3 * n + 1) / 2, где с - это количество необходимых карт.
Выглядит как квадратное уравнение. 3n^2 + n - 2c = 0.
Осталось взять какое-нибудь с, решить уравнение (n = (-b + sqrt(b^2 - 4ac)) / 2a), где n = целая часть положительного корня, пересчитать с (c -= n * (3 * n + 1) / 2). Продолжать, пока n >= 1, увеличивая счётчик домиков.
Код напиши сам. Всего хорошего.

1