L. Reflection
time limit per test
15 seconds
memory limit per test
1024 megabytes
input
reflection.in
output
standard output

You are given a line with equation x = y. you need to perform the following operation Q times.

  1. For the ith operation, you are given an integer x and you are requested to find and print the corresponding value of its y coordinate on the current graph (assume that it equals to yi ).
  2. After finding yi, you should reflect the right part of the current graph (with x coordinates greater than or equal to xi) on the horizontal line y = yi .

Note that each operation depends on all operations before it.

Input

The first line of the input is the number of test cases T, each test case starts with a line containing a single integer Q the number of operations, where 1 ≤ Q ≤ 105.

Each of the following Q lines represents a query with a single integer x, where 0 ≤ xi ≤ 105.

Output

For each test case output Q lines. Each of them contains the corresponding y value.

Example
Input
1
5
1
2
1
3
4
Output
1
0
1
1
2
Note

Here are some figures that illustrate the first 2 operations: