Sum of Divisors

Interview

Time limit1sMemory limit512 MB

Summary

Given N up to 10^6 and 10^5 test cases, compute g(N), the sum of the divisor sums f(y) for all y from 1 to N.

Level: Medium5 of 10
Topics: Math, Number theory, Prefix sum, Implementation
Solved: No attempts yet

Problem

For two positive integers A and B, a positive integer C satisfying A = BC is called a divisor of A. For example, the divisors of 2 are 1 and 2, and the divisors of 24 are 1, 2, 3, 4, 6, 8, 12, 24. The sum of divisors of a positive integer A is the sum of all divisors of A, written f(A). The sum of f(y) over all positive integers y less than or equal to x is written g(x).

Given a positive integer N, find g(N).

Input

The first line gives the number of test cases T (1 ≤ T ≤ 100,000). From the second line, each test case is given on its own line as a positive integer N (1 ≤ N ≤ 1,000,000).

Output

For each test case, print g(N) on its own line.

Examples1

Example 1
Input
```
5
1
2
10
70
10000
```
Expected output
```
1
4
87
4065
82256014
```