Cho ba số nguyên dương ~a, b, c~. Xét phương trình: ~ax + by = c~

Yêu cầu: Tìm số lượng cặp ~(x, y)~ là nghiệm của phương trình với ~x, y~ là hai số nguyên dương.

Input

• Một dòng chứa ba số nguyên dương ~a, b, c\ (a, b,c \le 10^9)~.

Output

• Một số nguyên duy nhất là số lượng cặp nghiệm nguyên dương của phương trình.

Sample Input 1

2 4 20

Sample Output 1

4

Sample Input 2

6 12 1800

Sample Output 2

149

Test 1, có 4 cặp nghiệm: ~2\times 2+4\times 4=20~, ~2\times 4+4\times 3=20~, ~2\times 6+4\times 2=20~, ~2\times 8+4\times 1=20~