A knight is located at the (black) origin of an infinite chessboard. Let f(n) define the number of black squares the knight can reach after making exactly n moves. Given n (0 <= n <= 10⁸), output f(n).

Input

The first line of the input contains a single integer T, the number of test cases (1 <= T <= 10⁶). Each test case consists of a single positive integer n.

Output

For each value of n in the input, print a single line containing.

Example

Input:
2
0
1

Output:
1
0