One day two friends Rocko and Hunter go to playground which in shape of regular connected polygon. They were confused about which game to play, suddenly Rocko comes with an idea of playing Catch Me If You Can. In this game what they are supposed to do is to start from a check post in the ground and then simultaneously move in opposite direction with different speeds (Rocko with speed x and Hunter with speed 2x). In each move they can hop to another check post. Note each check post is unit distance on periphery of polygon from another check post.

Now what they want to find is at what distance from start point will they meet. Since both Rocko and Hunter are bit poor in mathematics, so they want your help to find that distance for them.

Note they can't meet in middle of two check posts.

For example: suppose size of ground is 2 units.

1 move: Rocko: 1 → 2, and Hunter: 1 → 2 → 1

2 move: Rocko: 2 → 1, and Hunter: 1 → 2 → 1

Thus, 1 is meeting point and its distance from start is 1 - 1 = 0

Input

There is a single positive integer T (T <= 100000) on the first line of input which corresponds to the number of tests cases. Then T lines follow, each containing a number N which represents size of polygon field, where 0 < N <= 10^17

Output

T lines containing distance of meeting point from start.

Example

Input:
2
1
2

Output:
0
0