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
2015-07-10 11:59:54 Oasis
AC in 0.11s in one go..my 100th...:)
2015-07-05 23:51:01 DHEERAJ KUMAR
good problem :)
finally AC after 8 TLE's :)
storing prime number's less than n helps :D
2015-06-30 12:57:57 kp
another concept bagged :)
2015-06-28 15:11:09 :.Mohib.:
I like it!! Awsm que!! ;)
2015-06-18 14:23:39 saifullah
AC in one go!!
2015-06-17 18:12:25 [Mayank Pratap]
My 199th problem was so nice... AC in 0.3s
2015-06-14 15:51:57 jas.py
sieves+power of prime(in factorial)->AC
2015-05-26 18:45:53
Made it after tough job....
Time : 0.1s memory 2M
2015-03-26 10:00:23 vishwajit kumar vishnu
Getting wrong answer on test case 5. Can someone help :(
2015-03-23 17:12:58 Sue
a good problem :))
got AC with time=5.15, mem=995M :3
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.