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
2021-06-19 16:01:15
i got all the judges right except the master judge help
Edit:
use long for java instead of int

Last edit: 2021-06-20 12:53:45
2021-01-09 16:30:28 Rafail Loizou
TLE with O(sqrt(n)) solution and scanfs printf
2020-12-31 12:54:03
why i getting wrong answer ??upto test case 6 it showing correct.
2020-06-28 20:35:58 Shubham Jadhav
Beautiful Problem
2020-06-08 10:55:47
jut write down few test cases and observe. ex 12
2020-05-18 18:24:41
Awwwww AC finally :D 1.43s 4.3M O(2*sqrt(n))
Hint: U need a pen and some white papers, try(ex N = 71) writing all x,y then... See, x:=1 to sqrt(N) u can use a loop as normally. With extant part, u can see y:=sqrt(N)-1 to 1 . Using math here hehehe. Interesting thing is the input is too big.
2020-05-08 20:24:42
Hi, can anyone please help me to solve this question in O(sqrt(n)). I am trying hard and ablw to solve in n/2 but not in sqrt(n). Please tell how to solve this.
2020-04-04 17:01:50
tejas_vi: sumbit in PyPy: https://www.spoj.com/ranks/SUMPRO/lang=PYPY2.4

.. but first check if your code really goes through 500 tests for n ~ 10^9 in 0.01s.
2020-04-04 15:23:59
Its an Easy question but my python code is showing (time limit exceeded) but on ideone the following message pops ((Success #stdin #stdout 0.01s 7184KB)), idk whats wrong with SPOJ
2019-12-10 20:01:01
very good question !! must try
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.