ZYB's Game

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

$ZYB$ played a game named $Number Bomb$ with his classmates in hiking:a host keeps a number in $[1,N]$ in mind,then
players guess a number in turns,the player who exactly guesses $X$ loses,or the host will tell all the players that
the number now is bigger or smaller than $X$.After that,the range players can guess will decrease.The range is $[1,N]$ at first,each player should guess in the legal range.

Now if only two players are play the game,and both of two players know the $X$,if two persons all use the best strategy,and the first player guesses first.You are asked to find the number of $X$ that the second player
will win when $X$ is in $[1,N]$.

Input

In the first line there is the number of testcases $T$.

For each teatcase:

the first line there is one number $N$.

$1 \leq T \leq 100000$,$1 \leq N \leq 10000000$

Output

For each testcase,print the ans.

Sample Input

1 3

Sample Output

1

Hint

hujie

Source

BestCoder Round #65

提交代码