We have an infinite non-decreasing sequence A which is created as follows:

• A[1] = 1 and A[2] = 2.
• A number i occurs A[i] times in the sequence.

First few terms in the sequence are: { 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7... }. Note that 3 occurs 2 times in the sequence, (because A[3] = 2).

Your task is to find the term A[n] for any given n, where 0 < n <= 1e13.

Input

First line contains t, the number of test cases. Each of the next t lines contains a number n.

Output

For every case, print the nth term of the sequence.

Example

Input:
2
5
12

Output:
3
6