Given a proper rational irreducible fraction a / b. With this fraction, the following operation is performed: 1 is added to the numerator and denominator of the fraction, after which the fraction is reduced. Determine whether it is possible to obtain another proper fraction c / d from the fraction a / b using such operations.
The program receives four integers a, b, c, d as input, and 0 < a < b≤ 105, 0 < with < d≤ 105, numbers a and b are relatively prime, numbers c and d are relatively prime, a / b ≠ c / d.
The program should output one natural number – how many of the described operations need to be applied in order to get a fraction c / d from a fraction a / b. If this is not possible, the program should output the number 0.
|
Enter |
Output |
Note |
|
1
3
2
3
|
2 |
Given a fraction 1 / 3. After the first operation, a fraction is obtained
2 / 4, which is reduced to 1 / 2. After the second operation
it turns out the fraction 2 / 3.
|
|
2
3
1
3
|
0 |
It is impossible to get a fraction 1/3 from a fraction 2 / 3.
|