Mike and Mobile Keypad Problem

Mike, a young math enthusiast, is playing with his mom’s mobile phone, which has a keypad with 12 buttons (10 digits: 0-9, and 2 special characters: ‘*’ and ‘#’). His challenge is to find out how many different numbers he can generate by pressing exactly 'N' buttons. He follows these rules:

1. Mike only presses buttons with digits (0-9), never the ‘*’ or ‘#’.
2. The next button press must either be the same button or an adjacent button.
3. Initially, he can start pressing any button except ‘*’ or ‘#’.

Your task is to help Mike solve this problem, and due to potentially large results, output the answer modulo 10^9 + 7.

Input:

The first line of the input is an integer 'T', indicating the number of test cases.
Each of the next 'T' lines contains an integer N, the number of buttons to press.

Output:

For each test case, output the number of distinct numbers that can be formed by pressing exactly 'N' buttons on the keypad. Print each result on a new line.

Example:

Input:

2
1
2

Output:

10
36

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 5 * 104
• Time Limit: 1 second

Note:

You do not need to print anything; the function implementation will handle this itself.