Project Euler #137: Fibonacci golden nuggets

_{This problem is a programming version of Problem 137 from projecteuler.net}

Consider the infinite polynomial series , where is the term in the Fibonacci sequence: ; that is, , and .

For this problem we shall be interested in values of for which is a positive integer.

Surprisingly

The corresponding values of for the first five natural numbers are shown below.

We shall call a golden nugget if is rational, because they become increasingly rarer; for example, the golden nugget is .

Given , find the golden nugget. Since this number can be very large, output it modulo .

Input Format

The first line of input contains , the number of test cases.

Each test case consists of a single line containing a single integer, .

Constraints

In the first test case:
In the second test case:
In the third test case:

Output Format

For each test case, output a single line containing a single integer, the answer for that test case.

Sample Input

2
1
10

Sample Output

2
74049690