HZNUOJ

Chinese checkers

Tags:
Time Limit:  1 s      Memory Limit:   64 MB
Submission:41     AC:17     Score:98.93

Description

I think almost everyone play Chinese checkers when we were young.

Recently, hft777 is fond of playing Chinese checkers. But he is puzzled with how many steps at least to move all his pieces to his opposite position.

To make the problem simple, now we take a line into account. There are n positions on a line, numbered from 0 to n-1.At fast, two same balls is on 0 and 1 position, and every time you can move a ball left or right, or you can move a ball on the position x to the position z on the other side of the ball on the position y, and |x-y|=|y-z|. And you must mark sure the ball can’t move out of the bounder, and the two balls can’t be on one same position. Now, hft777 wants to how many steps at least to move the two same to the n-2, n-1 positions.

Input

The first line of the input is one integer t, the number of testcase.

For each testcase, one integer n for a line, corresponding to the length of the line.  2≤n<1000 

Output

For each testcase output the minimum steps.

Samples

input
2 3 4
output
1 2

Source

3rd Central South China Programming Contest