ABC Pvt. Ltd., needs to recruit some candidates and they want the test to be somewhat new, rather than the conventional way of asking questions in all areas. They have a logic, which converts one integer to another. Your task is to find the logic behind it and then solve the questions for certain inputs.

The question given by them is as follows:

The following are the output provided for the inputs given to one of our newly bought machines. You need to find the output that will be generated for the given inputs. Some sample input and output are:

   4 -> 1, 23 -> 29, 7 -> 7  16 -> 1

Your task is to find the machine's output for some inputs

Input

Input contains several integers, each in a single line.

Input ends with a -1

All inputs <= 10^16

Output

Output one integer for every input, as said above.

Example

Input:
4
7
23
-1

 Output:
1
7
29