B. Numbers on the Blackboard
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Note: You may want to use $$$64$$$-bit integers instead of $$$32$$$-bit integers in this task. For example, in Java, you may want to use long instead of int. In C++, you may want to use long long.

Yunli is writing numbers on the blackboard!

She first writes the number $$$1$$$ one time, then the number $$$2$$$ two times, then the number $$$3$$$ three times, and so on.

Then, Yunli gives you an integer $$$x$$$, and she wants you to tell her how many numbers she must write in this fashion until the sum of all numbers is at least $$$x$$$.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) – the number of test cases.

The first line of each test case contains an integer $$$x$$$ ($$$1 \leq x \leq 10^{18}$$$).

Scoring

Partial credits will be given to programs who pass tests with smaller constraints outlined below.

GroupPointsConstraints
115The sum of $$$x$$$ does not exceed $$$2\cdot 10^5$$$ over all test cases
230$$$x \leq 10^{9}$$$
355No further constraints
Output

For each test case, output the answer on a new line.

Example
Input
10
1
2
3
4
5
6
7
8
9
10
Output
1
2
2
3
3
4
4
4
5
5
Note

The first six numbers written are $$$1$$$, $$$2$$$, $$$2$$$, $$$3$$$, $$$3$$$, $$$3$$$.