Codeforces and Polygon may be unavailable from May 23, 4:00 (UTC) to May 23, 7:00 (UTC) due to technical maintenance. ×
A. Sakally Soldier
time limit per test
2 seconds
memory limit per test
256 megabytes
input
alimagde.in
output
standard output

Khaled is a sakally soldier. A sakally soldier is a soldier too lazy to do any duties during his service in the military.

One day during the morning assembly Sergeant Magde decided to choose some soldiers to be on duty.

The $$$N$$$ soldiers available will form a queue of $$$N$$$ positions numbered $$$1$$$ through $$$N$$$ where each soldier stands on one position.

Sergeant Magde will do the following:

When picking the $$$i^{th}$$$ soldier he will count $$$i$$$ positions starting from the last picked position (initially equal to $$$0$$$) then pick the soldier standing on that position.

Note that Sergeant Ali will only do the above operation if he can count $$$i$$$ positions.

Since Soldier Khaled is sakally, he decided to pick different positions from the ones Sergeant Ali will pick.

Your task is to help Soldier Khaled count how many different positions he can pick so that Sergeant Ali won't pick him?

Input

The first line consists of a single integer $$$T$$$ $$$(1 \leq T \leq 100)$$$, denoting the number of test cases.

Each test case contains a single integer $$$N$$$ $$$(1 \leq N \leq 10^9)$$$, denoting the number of soldiers.

Output

For each test case, print a single line containing a single integer denoting how many different positions Soldier Khaled can pick.

Example
Input
2
8
2
Output
5
1
Note

The answer of $$$8$$$ is $$$5$$$ since the picked soldiers will be $$${1, 3, 6}$$$, and then the remaining positions for Soldier Khaled are $$${2, 4, 5, 7, 8}$$$.

The answer of $$$2$$$ is $$$1$$$ since the picked soldiers will be $$${1}$$$, and then the remaining positions for Soldier Khaled are $$${2}$$$.