Amicable Numbers

Time limit1sMemory limit128 MB

Summary

For each N, print all pairs of distinct numbers up to N where each equals the sum of the other's proper divisors.

Level: Medium4 of 10
Topics: Number theory, Brute force, Implementation
Solved: No attempts yet

Problem

The two natural numbers 220 and 284 are called amicable numbers because they are different from each other and, for each one, the sum of its proper divisors (its divisors excluding the number itself) equals the other number. That is, the sum of the proper divisors of 220,

$1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284$

equals 284, and the sum of the proper divisors of 284,

$1 + 2 + 4 + 71 + 142 = 220$

equals 220.

Given a natural number, write a program that finds every amicable pair whose two members both do not exceed the given value.

Input

The input consists of several lines, each containing a single integer $N$ ( $0 < N \le 10^6$ ). The input ends with a line containing 0, which must not be processed.

Output

For each input value $N$ , print a header line reading Amicable numbers between 1 and N (with N replaced by the actual value). Then print every distinct amicable pair both of whose members lie between $1$ and $N$ , one pair per line, as the two numbers separated by a single space with the smaller number first. List the pairs in ascending order of their smaller member. If no such pair exists, print None instead. Separate the outputs for consecutive input values with a single blank line. A number cannot form an amicable pair with itself.

Examples1

Example 1

Input

100
300
0

Expected output

Amicable numbers between 1 and 100
None

Amicable numbers between 1 and 300
220 284