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
Shubham Jadhav: 2020-06-28 20:35:58

Beautiful Problem

ck_17: 2020-06-08 10:55:47

jut write down few test cases and observe. ex 12

hung02: 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.

landi58: 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.

nadstratosfer: 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.

tejas_vi: 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

surajmall: 2019-12-10 20:01:01

very good question !! must try

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~


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