DIVFACT - Divisors of factorial

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 109+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


Added by:ivar.raknahs
Date:2015-01-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Own

hide comments
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.