The Function

Given an positive integer N, compute the following function f(N):

Here x/i denotes integer division.

Since the F(N) can be quite large; please output F(N) % 1000000007.

Input

First line contains T, the number of test cases. Next T lines contain the value of N for each test case.

It is known that 1 ≤ T ≤ 50, 1 ≤ N ≤ 10^9.

Output

Output T lines, i-th line containing the answer for i-th test case.

Examples