Filling Diamonds
Time limit1sMemory limit1024 MB
Count the ways to cover a belt-shaped region of 4n-2 triangles with diamonds, for up to 10^4 queries with n up to 10^9.
- Level
Medium5 of 10
- Topics
- Combinatorics, Math
- Solved
- No attempts yet
Problem
You are given an integer . Count the ways to completely cover a belt-like region of triangles with diamond shapes.
A diamond is made of two triangles. You may move, rotate, or flip a diamond, but you may not scale it. Two coverings are different if there are two triangles that are covered by the same diamond in one covering but by different diamonds in the other.
See the pictures below. The diamond on the left is the shape you will use, and the region on the right is the one you need to fill.


The figures show the region for .
Answer independent test cases.
Input
The first line contains a single integer (), the number of test cases.
Each of the next lines contains a single integer ().
Output
For each test case, print the number of ways to fully cover the belt-like region of triangles with diamond shapes. Under the given constraints, this number does not exceed .
Hint
In the first test case, there are 2 ways to fill the region.

In the second test case, there is only one way to fill the region.
