The ? 1 ? 2 ? ... ? n = k problem#1542
Sign in

The ? 1 ? 2 ? ... ? n = k problem

1 second
128 megabytes
Hard

Given the following formula, you should place the operators '+' or '-' instead of each '?', in order to obtain a given :

? 1 ? 2 ? ... ? n = k

For example, to obtain k = 12, the expression will be:

- 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12, where n = 7.

Input

The first line contains the number of test cases. Each test case contains one integer (0 \leq |k| \leq 10^9).

Output

For each test case, print the minimal possible (1 \leq n) for which it is possible to obtain using the formula above.

Examples

Example 1

Loading
Loading