Tổng ước của mọi số từ 1 đến n (Sum of Divisors from One to N)

Nguồn: Phước Hưng OJ

Đề bài

Cho số nguyên dương $n$. Với mỗi số nguyên $i$ từ $1$ đến $n$, hãy tính tổng tất cả ước nguyên dương của $i$, bao gồm cả $1$ và chính $i$. Một số nguyên dương $d$ là ước của $i$ khi $i\bmod d=0$. Bài yêu cầu xử lý và in kết quả cho mọi số $i$ theo thứ tự tăng dần, không chỉ tính tổng ước của riêng $n$.

Input

Một dòng chứa duy nhất số nguyên dương $n$.

Output

In đúng $n$ dòng. Dòng ứng với $i$ gồm hai số nguyên i S, cách nhau đúng một dấu cách; $S$ là tổng các ước dương của $i$. Không có dòng tiêu đề.

Subtask

• Subtask 1 (20%): $1\le n\le10$.
• Subtask 2 (30%): $1\le n\le100$.
• Subtask 3 (50%): $1\le n\le1000$.

Ví dụ

Ví dụ 1

Input:

4

Output:

1 1
2 3
3 4
4 7

Giải thích:

Các tập ước lần lượt là {1}, {1, 2}, {1, 3} và {1, 2, 4}; tổng là 1, 3, 4 và 7.

Ví dụ 2

Input:

1

Output:

1 1

Giải thích:

Số 1 chỉ có một ước nguyên dương là chính nó.