For a given calculate the value of , where
Here means the greatest common divisor of integers and .
For those who have trouble understanding summation notation, the meaning of is given in the following code:
Consists of no more than lines. Each line contains one integer . Input is terminated by a line containing a single zero and should not be processed.
For each input number print in a separate line the corresponding value of . The value of fits in a -bit signed integer.