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
2018-06-28 11:48:36
really nice problem.......pen and copy can only save!!
2018-05-21 09:37:52
easy one comparing with those problems I met these days~
2018-05-12 18:16:01
This is a really nice problem.
2017-12-22 19:06:44
Nice one

Last edit: 2017-12-22 19:40:41
2017-06-14 21:37:48
only pen and copy can save you !!
2017-01-19 14:04:28
take all in long long int costed me 2 WA...
2016-09-20 17:47:39 Ashok
anybody in java got AC ?
2016-05-31 17:55:57
easy one

Last edit: 2016-05-31 17:58:25
2016-03-02 11:02:32
this problem is so easy but i don't understand why java wrong??? i test many cases and all are true
2016-02-29 17:02:13

how to fix errors time limit exceeded - java

Last edit: 2016-02-29 19:50:07
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.