- All Contests
- ProjectEuler+
- Project Euler #95: Amicable chains

# Project Euler #95: Amicable chains

# Project Euler #95: Amicable chains

_{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
```