Your guests loved the cheese pyramid on your charcuterie board from Stack It I, and now people from all over the globe are hiring you to make their cheese ball pyramids!

You are appraoched by ~N~ customers, who each have a different number of cheese balls ~X_i~ to arrange. For each customer, you must make as tall of a stack as possible. You want to stack the balls tetrahedrally, meaning that each layer is an increasingly shrinking equiltaterial traingle.

For example, a tetrahedron with height of 3 has 3 layers of cheese balls, and 6 + 3 + 1 = 10 balls in total.

When making your cheese ball tetrahedrons, you don't want to leave any layers incomplete. It's okay if you have some cheese balls spare, they will be unused.

Given ~N~ customers with different numbers of cheese balls, what is the tallest tetrahedron you can make for each of them?

Input

The first line of each test case contains an a single integer ~N~ ~(1 \leq N \leq 10^5)~, the number of customers who want you to make cheese ball pyramids.

The next ~N~ lines contains ~X_i~ ~(1 \leq X_i \leq 10^{15})~, the number of cheese balls the ith customer wants you to arrange into a pyramid.

Output

For each test case, print the tallest tetrahedron you can make out of your input.

Example

Input

3
10
9
20

Output

3
2
4

• With 10 cheese balls, you can make a tetrahedron of height 3 with 0 spare balls.

• With 9 cheese balls, you can make a tetrahedron of height 2 with 5 spare balls.

• With 20 cheese balls, you can make a tetrahedron of height 4 with 0 spare balls.