amicablecats

Problem Description

Rar the Cat lives in a house with many different cats. Each cat has a label ranging from 1 to the number of cats in the house. Rar the Cat, being a "single" cat, (yes, they do get married) is searching for a lifelong partner.

In Catlands, cats can only marry if they are amicable towards each other. Two cats can only be amicable if:
- The proper divisors of the label of the first cat add up to the label of the second cat.
- The proper divisors of the label of the second cat add up to the label of the first cat.

Rar the Cat wants to know who he can marry other than himself. Given N, Rar the Cat's label number, output his lifelong cat partner.
If there is no such number, Rar the Cat is destined to be forever alone. In this case, output "-1".

Input

The input should contain one integer, Rar the Cat's number.
The input will be terminated with a newline.

Output

The output should contain one integer, his partner's number, or "-1" if no such number exists.
The output should be terminated with a newline

Limits

Subtask 1 (20%): 1 <= N <= 1,000,000
Subtask 2 (80%): 1 <= N <= 1,000,000,000,000 (wahahaha)

Sample Input 1

220

Sample Output 1

284

Submitting to 'amicablecats'


You're not logged in! Click here to login


Submitting to 'amicablecats'


You're not logged in! Click here to login


Submitting .cpp to 'amicablecats'


You're not logged in! Click here to login


Compile Errors


							
Time Limit: 1 Seconds
Memory Limit: 512MB
No. of ACs: 80
Your best score: 0
Source: Dunjudge Archive

Subtask Score
1 20
2 80
3 0