Tổng ước riêng (Sum of Proper Divisors)

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

Phiên bản: Phước Hưng OJ Extended

Đề bài

Ước riêng của số dương n là một ước dương nhỏ hơn n. Tính tổng tất cả ước riêng của n. Nếu n=1 thì tổng bằng 0. Với n là chính phương, ước căn bậc hai chỉ cộng một lần.

Input

Một số nguyên n.

Output

Một số nguyên là tổng các ước riêng.

Subtask

• Subtask 1 (20%): 1 ≤ n ≤ 1000.

• Subtask 2 (30%): 1 ≤ n ≤ 10^6.

• Subtask 3 (50%): 1 ≤ n ≤ 10^9.

Ví dụ

Ví dụ 1

Input:

36

Output:

55

Giải thích: Các ước riêng là 1,2,3,4,6,9,12,18, tổng bằng 55.

Ví dụ 2

Input:

1

Output:

0

Giải thích: Số 1 không có ước riêng.