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