Background:
Mehta's friend Verma has challenged him in a maths puzzle. The puzzle involves playing with digits, their product and square root.

Task:
Numbers which have product of their digits as perfect square in their decimal representation are called Fancy Numbers. So, you have to report the count of Fancy Numbers having length less than or equal to given number N. Length of the number is defined as number of digits in its decimal representation.

Input:
First Line of the input contains number of test cases T.
Next T Lines contain a single number N denoting the maximum length.

Output:
Output the count of Fancy Numbers having length less than or equal to given number N in a separate line for all test cases T modulo 10⁹ + 7.

Note:
0 is a perfect square and has length 1.
Any number of length X does not have leading zeros i.e one is represented as 1 and not 01, 001.

Constraints:
Subtask 1:
1 <= T <= 10
1 <= N <= 10000
Subtask 2:
1 <= T <= 5
1 <= N <= 10¹⁸