A. Sum of Squares
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a well-known formula for the sum $$$f(n)$$$ of the first $$$n$$$ squares, $$$$$$f(n) = 1^2 + 2^2 + 3^2 + \ldots + n^2 = \frac{n(n+1)(2n+1)}{6}.$$$$$$

Write a function that computes $$$n$$$ given $$$f(n)$$$.

Input

The first line of input contains a single integer $$$T$$$, the number of test cases $$$(1 \leq T \leq 10\,000)$$$. Each of the following $$$T$$$ lines contain a single integer $$$k$$$ $$$(1 \leq k \leq 2^{60})$$$.

Output

For each test case, print a line with the positive integer $$$n$$$ satisfying $$$f(n) = k$$$. It is guaranteed that such an integer exists.

Example
Input
5
1
5
14
385
1152919708258615990
Output
1
2
3
10
1512307
Note

Hint: the largest possible value of $$$n$$$ with $$$f(n) \leq 2^{60}$$$ is $$$n=1512307$$$.