An evil professor has just assigned you the following problem. A sequence is defined by the following recurrence:
For each value compute the value .
Consists of a number of lines, each containing one integer , no less than and no greater than . Input is followed by a single line containing the integer . This last line is not a value of and should not be processed.
For each value of (but not the final ) output the corresponding value of modulo .