Maggu has a wire of length n. He has to make triangles out of it such that the side lengths of each triangle are integers. He now wants to know the number of distinct (not congruent) triangles that he can create using the wire of length n. Note that he has to use all of the wire in making the triangle.

Input

First line contains T: number of test cases. (1 <= T <= 10^5)
For each test case, there is a single line containging an integer n (n >= 1 && n <= 10^9)

Output

Each test case output a single integer representing the number of triangles he can create.

Example

Input:
3
5
7
9
Output:
1
2
3