Chinese checkers

Time Limit: 1000 ms

Memory Limit: 65536 ms


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.


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


For each testcase output the minimum steps.

Sample Input


Sample Output




3rd Central South China Programming Contest