A regular octagon with vertices X1, X2,..., X8 is provided. A frog starts jumping from the vertex X1. It may jump to any of the two adjacent vertices in one jump except from X5. When it reaches X5, it stops and stays there. Let P(n) be the number of distinct paths of exactly n jumps ending at X5. Given the value of n, you need to print the value of P(n).

Input
The first line of the input contains the number of test cases T, at most 100. Each of the next T lines contain a single integer N, where 1 ≤ N ≤ 100.

Output
For each value of N in the input, print on a new line the number of distinct paths of exactly n jumps ending at X5.

Example

Input:
3
1
2
4

Output:
0
0
2

见题面

见题面