A Square free number is a number whose sum of every adjacent two digits is not a perfect square and doesn'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 test cases.

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¹⁸.

Example

Input:
3
1
2
3
Output:
6
67
501

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