B. Modular MEX
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$. Find the smallest non-negative integer that isn't present in $$$n \bmod 1$$$, $$$n \bmod 2$$$, $$$n \bmod 3, \ldots, n \bmod n$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

The first and only line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^9$$$).

Output

For each test case, output an integer  — the answer to the problem.

Example
Input
3
1
3
2
Output
1
2
1
Note

In the first test case, $$$[1 \bmod 1] = [0]$$$, hence the smallest non-negative integer that isn't present here is $$$1$$$.

In the second test case, $$$[3\bmod1, 3\bmod2, 3\bmod3] = [0, 1, 0]$$$, hence the smallest non-negative number that isn't present here is $$$2$$$.