Sum of Divisors from One to N

Source: Phước Hưng OJ

Problem Statement

Given a positive integer n, compute the sum of ALL positive divisors of each integer i from 1 through n. Both 1 and i are included. A positive integer d divides i if i modulo d is zero. Output the result for EVERY i in increasing order, not just for n.

Input

One line containing a single positive integer n.

Output

Print exactly n lines. The line for i has two integers i S separated by a single space; S is the sum of all positive divisors of i. Do not print a header.

Subtasks

• Subtask 1 (20%): 1 <= n <= 10.
• Subtask 2 (30%): 1 <= n <= 100.
• Subtask 3 (50%): 1 <= n <= 1000.

Examples

Example 1

Input:

4

Output:

1 1
2 3
3 4
4 7

Explanation:

The positive divisors are {1}, {1,2}, {1,3}, and {1,2,4}, giving sums 1,3,4,7.

Example 2

Input:

1

Output:

1 1

Explanation:

The only positive divisor of 1 is 1.