Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3266
Strange PingPong Game

Time Limit: 5 Seconds      Memory Limit: 32768 KB

DD and his girlfriend love a strange pingpong game. The rules are as follows:

1. If their points are not relative primes, they will reduce them to relatively prime. (If someone is 0 point, it is legal too.)

2. If someone reachs k points first after reduction, he/she will win the game.For example, a possible game can be:

1:1 -> 1:2 -> 1:1(2:2) -> 2:1 -> 3:1 -> 4:1 -> 2:1(4:2)
DD's girlfriend says that if the score can be a special one, she will give DD a special gift(~.~) As you guess, DD wants to reach that point as soon as possible. He also wonders whether the score can be reached. So he asks for your help to calculate the minimum steps to reach that score.


This problem contains MANY test cases(up to 350). You should process to the end of file.

For each case, the first line is a single integer k (1 <= k <= 1000) The second line contains two integers a b(0 <= a, b <= k), giving the score.


For each test case, you should only output one integer which indicates the minimum steps to get to the score. If it is impossible, output -1.

Sample Input

1 1
3 4

Sample Output


Author: WANG, Naiyan
Source: ZOJ Monthly, November 2009
Submit    Status