J. Epic Fight
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

George is so excited to see an epic fight between the legends Ahmad and Yaman.

George gives them $$$n$$$ cells that are numbered from $$$1$$$ to $$$n$$$ where each cell $$$i$$$ and $$$i+1$$$ $$$(1 \le i \le n-1)$$$ are connected by a two-way road to play a game on them.

The game is going as follows: First of all, Yaman will choose a cell to put an egg on it and mark it as a visited cell, then they will take turns starting from Ahmad as follows:

  • The player will move the egg to an adjacent cell that is not visited yet and mark it as visited.
The player who can't move the egg will $$$\bf{lose}$$$ the game.

Now Yaman is wondering how many cells he can choose so he can win.

Input

The first line contains the number of test cases $$$t$$$ $$$( 1 \le t \le 10^{5} )$$$. A description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$( 1 \le n \le 10^{18} )$$$ indicating the number of cells.

Output

A single integer represents the number of winning starting cells for Yaman.

Example
Input
4
1
3
777
2
Output
1
2
389
0