Do It!

Time Limit: 0.5 sec

 

The Problem

One day two friends Habib and Karim go to playground which in shape of regular connected polygon. They were confused about which game to play, suddenly Habib 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 (Habib with speed x and Karim 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 Habib and Karim 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.

 

Ex: suppose size of ground is 2 units. 

1 move: Habib: 1->2 and Karim: 1->2->1

2 move: Habib: 2->1 and Karim: 1->2->1

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

 

The 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.

 

The Output

For each test case print the distance of meeting point from start in separate line.

 

Sample Input

3

2

6

1

 

Sample Output

0

2

0

 

 

 

Inter University Programming Contest - 2016 [BGC Trust University Bangladesh]

Problem Setter:  Bishwajit Barua