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^9 + 7.

Each output in new line.

Constraints

T <= 30

N <= 10^17

Example

Input:
1
2

Output:
62