A Square free number is a number whose sum of every adjacent two digits is not a perfect square and dosen't contain digit 0. For example, 123 is a square free number cause sum of first two adjacent digits 1 + 2 = 3 is not a perfect square and sum of last two adjacent digits 2 + 3 = 5 is not a perfect square.

You are given an integer n. You have to calculate the number of n-digit square free number.

As the result can be very big, output the result modulo 1000000007 (1e9 + 7) ;

Input

First line of the input contains a number T, the number of testcase.

Each of the next T lines will contain an integer n .

Output

Output the number of square free numbers of length n .

Constraints:

T <= 1000.

1 <= n <= 10^{18 .}

Example

Input:

3

1

2

3

Output:

6

67

501

Note: By definition 1, 4, 9 is not square free number.