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 answer to corresponding test case.

Example

Input:

3
2
4
6

Output:

4
15
33
Constraints:
1 ≤ T ≤ 500
1 ≤ N ≤ 109

Sample 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

 


hide comments
anirudnits: 2019-01-03 18:38:37

if you're stuck https://codeforces.com/problemset/problem/616/E.

Last edit: 2019-01-03 19:07:02
sanjana_17: 2018-06-28 11:48:36

really nice problem.......pen and copy can only save!!

nimphy: 2018-05-21 09:37:52

easy one comparing with those problems I met these days~

quachtridat: 2018-05-12 18:16:01

This is a really nice problem.

xynkt_99: 2017-12-22 19:06:44

Nice one

Last edit: 2017-12-22 19:40:41
sandeep_4141: 2017-06-14 21:37:48

only pen and copy can save you !!

cs_abhi2000: 2017-01-19 14:04:28

take all in long long int costed me 2 WA...

Ashok: 2016-09-20 17:47:39

anybody in java got AC ?

karthik1997: 2016-05-31 17:55:57

easy one

Last edit: 2016-05-31 17:58:25
Erhee: 2016-03-28 11:17:19


Last edit: 2018-02-06 14:21:53

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