DIVSUM2 - Divisor Summation (Hard)


Given a natural number n (1 <= n <= 1e16), please output the summation of all its proper divisors.

Definition: A proper divisor of a natural number is the divisor that is strictly less than the number.

e.g. number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22.

Input

An integer stating the number of test cases (equal to 500), and that many lines follow, each containing one integer between 1 and 1e16 inclusive.

Output

One integer each line: the divisor summation of the integer given respectively.

Example

Input:
3
2
10
20

Output:
1
8
22
warning: a naive algorithm may not run in time.

hide comments
des1997: 2018-06-23 11:50:33

ran in 3.02 seconds:)

karthik1997: 2017-12-28 13:39:05

Can't go below 2s . :(

kmkhan_014: 2017-12-21 16:55:26

this is extremel !!! AC in 15s

mastik5h_1998: 2017-06-23 07:40:49

very annoying question.......
lot of wrong ans...

oualiamine: 2017-03-20 22:12:50

what does 1e16 means?

=(Francky)=> 1×10¹⁶

Last edit: 2017-03-21 08:12:14
kira28: 2017-01-04 21:13:04

Finally !!!!
xD

square1001: 2016-07-26 06:21:28

I got 4.90 sec!
The time complexity is O(n^0.5 log n + qπ(n^0.5)).

nightwolf_9197: 2016-02-19 13:15:56

Bin Jin please check my submission as it takes <2seconds on ideone.com but here it shows tle

ashish kumar: 2015-12-26 15:24:25

I am using optimized sieve with miller rabin test to check for prime and a sqrt time divisor function after all my time is about 4.5 secs. But @Lakshman and some other they got exceptionally less time . How it is possible?

Bhuvnesh Jain: 2015-07-22 06:00:51

Done

Last edit: 2016-09-29 13:54:35

Added by:Bin Jin
Date:2007-08-29
Time limit:18.17s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: CPP
Resource:own problem