Johnny (not little anymore) is a super agent .He is been following up on leads against the world’s worst terrorists. He got a intel that a terrorist is staying at an expensive hotel. Only thing that stops LJ is the secure door in the room entrance.

The secure door had a lock which resembled this,

The enter key cannot be a part of the pass-code

When Johnny did some spy work on it, he found out that every pair of neighbouring digits in the pass code is adjacent on the keypad. Adjacent means that the digits share a common edge.

Now he wants to know how many different possibilities are there for the pass code so that he can bring a computer accordingly to hack the lock.

Input

Input begins with single integer ‘T’ denoting number of test cases and T lines follow. Each line contains the number ‘N’ denoting the length of the pass code.

Output

For each test case T, output the number of different possibilities in a new line. Since the answer can be huge output the number mod 1000000007.

Constraints:

1 <= T <= 1,000

1 <= N <= 100,000

Sample

Input: 
2
3
25

Output:
74
478325846