Problem Description
There is an equilateral triangle consist of 3 mirrors. There is a tiny slit in the corners of the triangle, which can let a laser beam pass through.
We label the 3 slits as A, B and C. There only exists two ways (see the picture above) make a laser beam enter our triangle though C, reflects 11 times in ther triangle, and exit from the triangle though C. The 2 ways are symmetry.
Here is the question for you, our great programmer. How many ways we can make a laser beam enter the triangle though C and exit though C, and the beam reflects n times in the triangle? e.g. there are 80840 ways when n is 1000001.
Input
The first line contains a number T.(1≤T≤100) Then the following T line each line contains a number n.(1≤n≤107)
Output
For each n, print the corresponding result.
Sample Input
10
2
5
7
11
13
17
19
23
29
31
Sample Output
0
0
2
2
2
0
4
4
2
6