Programming Problem #21
"Bisquares"

A positive integer is called a bisquare if it is the sum of two squared positive integers. For example, 5 is a bisquare since 1^2+2^2=5; 34 is a bisquare since 5^2+3^2=34; and 8 is a bisquare since 2^2+2^2=8. However, 12 is not a bisquare. The five smallest bisquares are 2, 5, 8, 10 and 13.

A sequence of integers is called an arithmetic progression if the difference between any two consecutive numbers is the same. For example, '2,4,6,8,10' is an arithmetic progression of length 5; '3,9,15,21' is an arithmetic progression of length 4; '7,8' is an arithmetic progression of length 2; and '2,5,8' is an arithmetic progression of length 3. Note that each number in the arithmetic progression '2,5,8' is a bisquare. Given a positive integer N, your job is to output the longest arithmetic progression of bisquares in the range 1..N.

The input consists of one or more lines, each of which contains a single nonnegative integer N no greater than 5000. If N=0 it signals the end of the input. For each value of N, display a single line containing the longest arithmetic progression of bisquares in the range 1..N. The numbers must be separated by a space and must be in ascending order. If there are two or more arithmetic progressions of maximal length, output any one of them.

Input must be read from the file "prob21.in", and output must be written to the file "prob21.out". All output to the screen will be ignored.

Example Input

<BOF>
4
17
0
<EOF>

Example Output

2
2 5 8
A version of this problem originally appeared in the 1989 Pacific regionals.

Dr. Eric Shade