친화수

두 자연수 220과 284는 서로 친화수(amicable numbers) 라고 불린다. 두 수가 서로 다르면서, 각 수의 진약수(자기 자신을 제외한 약수)의 합이 상대 수와 같기 때문이다. 즉, 220의 진약수의 합

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

은 284이고, 284의 진약수의 합

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

은 220이다.

자연수 하나가 주어질 때, 두 수가 모두 그 값을 넘지 않는 모든 친화수 쌍을 찾는 프로그램을 작성하라.

입력은 여러 줄로 이루어지며, 각 줄에는 정수 $N$ ($0 < N \le 10^6$)이 하나씩 주어진다. 입력의 끝은 값이 0인 줄로 표시되고, 이 줄은 처리하지 않는다.

각 입력값 $N$에 대해, 먼저 Amicable numbers between 1 and N이라는 머리글 줄을 출력한다(N은 실제 값으로 바꾼다). 이어서 두 수가 모두 $1$ 이상 $N$ 이하인 서로 다른 친화수 쌍을 한 줄에 하나씩, 작은 수를 앞에 두고 두 수를 공백 하나로 구분하여 출력한다. 쌍은 작은 수를 기준으로 오름차순으로 나열한다. 그런 쌍이 하나도 없으면 대신 None을 출력한다. 서로 다른 입력값의 출력 사이에는 빈 줄 하나를 넣어 구분한다. 한 수는 자기 자신과 친화수 쌍을 이룰 수 없다.