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".
The input should contain one integer, Rar the Cat's number.
The input will be terminated with a newline.
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
Subtask 1 (20%): 1 <= N <= 1,000,000
Subtask 2 (80%): 1 <= N <= 1,000,000,000,000 (wahahaha)