You play a jumping game with the following rules: You are initially at coordinate 0 and turn 0, on turn i-th you jump one step to the right or to the left with length i . Calculate the minimum number of turns you need to get to X given in advance.

Input

First line: contains positive integer Q is the query number (1≤Q≤1e5) .

Next Q lines: each line contains an integer X(|X|≤1e9) .

Output Including Q lines, each containing the result of a query.

[image]

Input:

4

1

-2

3

-4

Output:

1

3

2

3

I just thinking about go BFS but 1e9 is very large number, anyone have another approach better plss help me. Thanks!