SFN - Square Free Number

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 <= 1018.

Example

Input:
3
1
2
3

Output:
6
67
501

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


Added by:Prodip
Date:2019-05-02
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2020-08-30 06:28:22
Digit DP

Last edit: 2021-03-13 04:24:19
2020-06-19 09:03:41
O(T * log(N) [* 10^3]) solution via matrix exponentiation.
got AC after an hour !!!
2019-05-09 18:34:26 mehmetin
n <= 2147483647 for all cases.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.