This problem is a programming version of Problem 95 from projecteuler.net
The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of are and . As the sum of these divisors is equal to , we call it a perfect number.
Interestingly the sum of the proper divisors of is and the sum of the proper divisors of is , forming a chain of two numbers. For this reason, and are called an amicable pair.
Perhaps less well known are longer chains. For example, starting with , we form a chain of five numbers:
Since this chain returns to its starting point, it is called an amicable chain.
Find the smallest member of the longest amicable chain with no element exceeding .
Input Format
First and only line contains
Constraints
Output Format
Print the corresponding answer.
Sample Input
10
Sample Output
6