Asutosh is very passionate about numbers. he has found a new type of numbers and calls them 'truncky numbers'.

He has challenged his friend Shantanu to find the sum of first n truncky numbers. As Shantanu is weak at programming, help him to complete his challenge.

A truncky number is defined as:

1. sum of digits in the number is of the form (5×k + 1) where k = number of digits.
2. absolute difference between any two digits in the number is either 0 or 1.
3. digits are in the non decreasing order.

Input

the first line contains T (number of test cases). Each test contains only one integer n.

Output

Print in single line sum of first n truncky numbers modulo 10⁹ + 7.

Each output in new line.

Constraints

T ≤ 30

N ≤ 10¹⁷

Example

Input:
1
2
Output:
62