Lucky Numbers

Lucy and Lily are twin sisters. Mr. Smith, their father, a mathematician, gave each of them a lucky number (positive integer) when they were born, and the two lucky numbers have only one common divisor, of course, it is 1.

Mr. Smith is extremely excited to see that his two little children are so interested in math and both of them show amazing talent. Mr. Smith now will teach the two little girls to do multiplication. He wants to start with the two lucky numbers a and b.

Mr. Smith will write a set of positive integers (we call it SetA) such that for any positive integer m, we can find m*a or m*b in SetA. Because Lucy and Lily can only count from 1 to M, so if m*a or m*b is larger than M, Mr. Smith will ignore m.

Mr. Smith wants to write least numbers.
So help him to figure out the minimum number of elements in SetA.
For example the lucky numbers are 3 and 2, and M is 7.
Mr. Smith could write 3,6,2,4. He could also write only 3,6,4 or 3,6 or 2,4. But in no way could he write only one number contain both (1*3 or 1*2) and (2*3 or 2*2).

The input has multiple cases, process to EOF. There are about 10000 cases.
Each case contains a line with 3 positive integers: a b M as described above.
We ensure the greatest common divisor of a and b is 1.
M, a, b are all fit 32bit integers.

For each test case, output a line with only one integer, the minimum number of elements in SetA.

3 2 7
4 3 8

2
2

zhanyu

2011 Multi-University Training Contest 5 - Host by BNU