SUMPRO - SUM OF PRODUCT

Given a number N, find the sum of all products x * y such that N / x = y (integer division).

Since the sum can be very large, please output this modulo 1000000007.

Input

The first line of input file contains an integer T, the number of test cases to follow. Each of the next T lines contain an integer N.

Output

Output T lines containing the answer to corresponding test case.

Example

Input:
3
2
4
6

Output:
4
15
33

Constraints:

1 ≤ T ≤ 500
1 ≤ N ≤ 109

Explanation

Case #1:

2 / 1 = 2
2 / 2 = 1
Answer = 1 * 2 + 2 * 1 = 4

Case #2:

4 / 1 = 4
4 / 2 = 2
4 / 3 = 1
4 / 4 = 1
Answer = 1 * 4 + 2 * 2 + 3 * 1 + 4 * 1 = 15


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

hide comments
2016-01-12 23:09:13 Arpan Mukherjee
Thanks @anuj0503 :D your hints just made the day :p
2016-01-03 18:59:42
nice problem.. long long int is working fine
2015-12-15 13:41:44 Shubhransh Srivastav
use unsigned long long int... cost me a tle with long long despite using O(sqrt(n)) solution....

Last edit: 2015-12-15 13:42:21
2015-12-11 08:10:44
HINT:1. If you divide a number say N, by any number less than N ( from 1 to N-1 ), the Quotient will be in range of 1 to sqrt(N).
2. All the Quotient repeat within range.
2015-12-05 10:06:27
o(sqrt(n)) with long long int AC:-)


Last edit: 2015-12-05 10:06:56
2015-11-28 16:56:01 bka
good question ;)
2015-10-12 17:06:54
can i check someone's else submission???plz tell
how to achieve O(sqrt(n))

Last edit: 2015-10-12 17:21:46
2015-08-22 12:12:51
nice !!

Last edit: 2015-08-22 12:40:30
2015-06-05 21:07:28 Abhay Jain
Got an AC! But time of 0.75. Trying to figure out how to optimize it better
2015-05-25 21:52:08 Vaporeon
Awesome Maths here!! loved it! :D :* D:
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.