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