Triangle Number Sums

A triangle number is a positive integer of the form 1+2+\dots+k. The first triangle numbers are 1, 3, 6, 10 and 15. Every positive integer can be represented as a sum of triangle numbers. For example, 42=21+21 and 1337=1326+10+1. Given a positive integer n, determine the smallest number of triangle numbers that sum to n.

Input

The first line has an integer t: the number of tests. After that, each line has a positive integer n.

Output

For each test, print the smallest number of triangle numbers.

Constraints

$1 \le t \le 100$

$1 \le n \le 10$^{12}$

Example

Input

5
1
2
3
42
1337

Output

1
2
1
2
3