Sum of Proper Divisors

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Compute the sum of positive divisors strictly below n. For n=1 return 0; count the square-root divisor once.

Input

One integer n.

Output

The sum of proper divisors.

Subtasks

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

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

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

Examples

Example 1

Input:

36

Output:

55

Explanation: The proper divisors of 36 sum to 55.

Example 2

Input:

1

Output:

0

Explanation: One has no proper divisors.