In the collection 100 zadań (100 Problems) by a famous Polish mathematician Hugo Steinhaus there is the following problem:

Prove that if we substitute any positive integer by the sum of squares of its digits, then we substitute the obtained new number by the sum of squares of its digits, and so on, then after a finite number of repetitions of that operation we will obtain the number 1 or 4.

Example

Task

1. Justify that the following informal algorithm:

   while n<>1 and n<>4 do n:=SumOfDigitSquares(n)

   has the halting property, i.e. for every natural n it halts after some finite time.

   You are supposed to use a computer in the proof, but you certainly cannot test all the natural numbers. A justification written on a sheet of paper is an important part of the solution to the problem.

2. Write a program that successively reads positive integers from the text file KWA.IN and for each of them generates and writes a result to the text file KWA.OUT. The result for n is a sequence of distinct numbers, beginning with n and ending with the number 1 or 4, every consecutive number of which, except the first one, is the sum of the squares of digits of the previous number in this sequence. The program should complete the task even for very big natural numbers n < 10⁶⁶.

At the beginning of your program, in a comment, give your last and first name, and the number of your working stand.

The input file KWA.IN is always nonempty and contains positive integers in a decimal form (at most 66-digit ones). There is a space or a single end-of-line character between consecutive numbers, and immediately after the last number there is an end-of-file character. The data is written faultlessly and your program needs not check its correctness.

The output file KWA.OUT should contain sequences generated for the numbers read from the file KWA.IN. Consecutive numbers of every sequence should be separated by a space or a single end-of-line character. Two consecutive sequences should be separated by an empty line, and immediately after the last element of the last sequence there should be an end-of-file character. Nothing else should be written in the file.

Examples

For the file KWA.IN:

33 17 638(end-of-file character)

33 18 65 61 37 58 89 145 42 20 4
(empty line)
17 50 25 29 85 89 145 42 20 4
(empty line)
638 109 82 68 100 1(end-of-file character)

89(end-of-file character)

89 145 42 20 4(end-of-file character)

Your program should look for the file KWA.IN in the current directory and create the file KWA.OUT also in the current directory. The source file containing the program written by you should be named KWA.???, where ??? are substituted by at most three-letter abbreviation of the programming language used. The same program in an executable form should be saved in a file KWA.EXE. Both the files should be stored on a hard disk and on a floppy disk.

The solution to the problem consists of a program - only one - in a source and executable form, stored, satisfying the above rules, on a hard disk and on a floppy disk. The solution should also contain a written justification that the informal algorithm formulated in the point 1 of the task has the halting property.