Professor Lazy, Ph.D.

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Professors are very motivated when they have to travel abroad for a conference (of course, if fees are paid by the university), but they don’t have the same attitude when the moment to grade exams arrives.

Professor Lazy, Ph.D., has a particular way to grade exams (and very unfair, by the way). He puts all his exams in a box and then starts getting them out one by one in a totally random fashion. He assigns grade α to the first exam that he gets out of the box, and grade β to the second exam that he gets out of the box. From that point on, he assigns a grade to each of the exams based on the grades of the previous two exams. What he does is that he takes the grade of the immediately previous exam, adds 1 and divides by the grade of the exam before the previous one.

For example, let’s imagine that α = 2 and β = 3. This is what happens:

·        The first exam gets α = 2.

·        The second exam gets β = 3.

·        The previous two grades are α and β, so the third exam gets  = = 2.

·        The previous two grades are β and , so the fourth exam gets = = 1.

·        The procedure continues until he’s done with all exams.

More formally, we can define the grade Qn of the nth exam with a recurrence like this:

Qn                         =

 

 

Even this simple procedure is a lot of work for Professor Lazy, Ph.D., so he asks you to write a program to do it for him. He wants to spend all day long drinking coffee in the cafeteria with other professors. Given α, β and n find the value of Qn.

Note that the grades do not necessarily lie inside a fixed range. They are just arbitrary integers.

 

Input

 The input contains several test cases (at most 1000). Each test case is described by three integer numbers α, β and n on a single line (1 ≤α, β ≤ 109 and 0 ≤ n ≤ 109).

The last line of the input contains three zeros and should not be processed.

Output

 For each test case, write the value of Qn in a single line. The input will be such that the value of Qn is always an integer. Furthermore, Qiwill never be zero for 0 ≤ i ≤ n (in other words, division by zero will never arise when evaluating the recurrence).

Sample Input

1 1 0
1 2 1
5 9 2
2 3 3
7 4 4
0 0 0

Sample Output

1
2
2
1
2

Hint

 

Source