Coin System

Time limit2sMemory limit512 MB

Summary

Given A, B and X, count the values Y so that coins X and Y generate exactly the same set of prices as A and B, or print -1 if infinitely many.

Level: Medium7 of 10
Topics: Number theory, Math, Greedy
Solved: No attempts yet

Problem

In the country where Youngsun lives, there are two kinds of coins, A and B. Every product in this country has a price of the form $A \times p + B \times q$ ( $p$ and $q$ are non-negative integers), so these two coins are enough.

One day Youngsun wondered whether a different coin system could also make the price of every product in this country.

Given A, B, and X, write a program that finds the values of two coins that can make every price of the form $A \times p + B \times q$ . One coin has value X and the other has value Y ( $Y \neq X$ ). Since X is given in the input, the task is to find Y. In the new system each coin can also be used any non-negative integer number of times, and Y is a positive integer.

Input

The first line contains A, B, and X. ( $1 \le A, B, X \le 200$ )

Output

Print the number of possible values of Y on the first line. If there are infinitely many possible values of Y, print -1.

Examples4

Example 1
Input
```
5 8 5
```
Expected output
```
5
```
Example 2
Input
```
8 4 2
```
Expected output
```
-1
```
Example 3
Input
```
7 4 13
```
Expected output
```
1
```
Example 4
Input
```
47 74 44
```
Expected output
```
2
```