Given a number, find the total number of divisors of the factorial of the number.

Since the answer can be very large, print answer modulo 10⁹+7.

Input

The first line contains T, number of testcases.

T lines follows each containing the number N.

Output

Print T lines of output each containing the answer.

Example

Input:
3
2
3
4
Output:
2
4
8

Constraints

1 <= T <= 500

0 <= N <= 50000