408496: GYM103158 A Sakally Soldier

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Sakally Soldiertime limit per test2 secondsmemory limit per test256 megabytesinputalimagde.inoutputstandard 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.

ExampleInput
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}$$$.

Source/Category

加入题单

算法标签: