Kevin was reading about various types of numbers like palindromes, primes, Fibonnaci and many more and got fascinated with them . Therefore he came with a special type of a number, which he called as a “divine” number. 

For a given positive integer to be divine it must satisfy both of the following conditions:

•  no two consecutive digits are equal, and
•  the last digit is a prime.
• The numbers cannot contain extra leading zeroes (that is, the number can begin with 0 if and only if this number is exactly one character '0'). For example, 007, 01 and 00099 are not valid numbers. 

Kevin wants to find how many divine numbers with $N$ digits exist and goes to Nick for help. Nick agrees to help his brother out, but actually is busy wooing Priyanka(because that is what people do after clearing JEE) and doesn’t have the time. Therefore he asks you to solve it for him so that he can come across as a responsible elder brother and all while get Priyanka .

Input 
• The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.

• The first and only line of each test case contains a single integer $N$ .  

Output 
For each test case, print a single line containing a single integer — number of $N$-digit positive divine numbers later modulo $10^9+7$. 

Constraints 
• 1 ≤ $T$ ≤ $10^5$ 

 • 1 ≤$N$ ≤ $10^{18}$
 

Problem Setter:  Shivam Jadhav