- All Contests
- ProjectEuler+
- Project Euler #202: Laserbeam

# Project Euler #202: Laserbeam

# Project Euler #202: Laserbeam

_{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
```