Число трикутника — це натуральне число у вигляді ~1+2+\dots+k~. Перші числа трикутника: 1, 3, 6, 10 і 15.

Кожне натуральне число можна представити у вигляді суми чисел трикутників.

Наприклад, 42=21+21 і 1337=1326+10+1.

Дано натуральне число ~n~. Визначте найменшу кількість чисел трикутника, сума яких дорівнює ~n~.

Обмеження

• ~1 \le t \le 100~
• ~1 \le n \le 10^{12}~

Формат вхідних даних

У першому рядку є ціле число ~t~: кількість тестів.

Після цього кожен рядок має натуральне число ~n~.

Формат вихідних даних

Для кожного тесту виведіть найменшу кількість чисел трикутника.

Приклад вхідних даних

5
1
2
3
42
1337

Приклад вихідних даних

1
2
1
2
3