This problem is a programming version of Problem 202 from projecteuler.net
Three mirrors are arranged in the shape of an equilateral triangle, with their reflective surfaces pointing inwards. There is an infinitesimal gap at each vertex of the triangle through which a laser beam may pass.
Label the vertices , and . There are ways in which a laser beam may enter vertex , bounce off surfaces, then exit through the same vertex: one way is shown below; the other is the reverse of that.
There are ways in which a laser beam may enter vertex , bounce off surfaces, then exit through the same vertex.
In how many ways can a laser beam enter at vertex , bounce off surfaces, then exit through the same vertex?
Input Format
First line of each test file contains a single integer which is the number of queries per this file. lines follow each containing a single integer that is the corresponding number of surfaces laser beam should bounce off.
Constraints
Output Format
Output exactly lines with the answer for the -th query on -th line.
Sample Input 0
2
11
1000001
Sample Output 0
2
80840