Tile Filling

Time limit1sMemory limit128 MB

Summary

Count the number of ways to tile a 4×N board with 2×1 dominoes for multiple queries, bounded so the answer fits in a 32-bit integer.

Level: Medium6 of 10
Topics: Dynamic programming, Math, Combinatorics
Solved: No attempts yet

Problem

You are given a rectangular board with height 4 and width N. Fill it completely with dominoes of size 2×1 or 1×2. Dominoes may not overlap or extend outside the board.

For each given N, output the number of different tilings of the board.

Input

The first line contains the number of test cases T. T is a natural number no greater than 1,000. Each of the next T lines contains one integer, the width N of the board. N is a natural number.

Each N is chosen so that the number of tilings is at most 2,147,483,647.

Output

For each test case, output the number of ways to tile a board of height 4 and width N, one per line.

Examples1

Example 1
Input
```
3
2
3
7
```
Expected output
```
5
11
781
```