A gigantic amount of space stations has been built in the deep space. Space ships that can travel in the space at the speed closed to the speed of light are also available. Although space ships can travel extremely fast, they cannot go directly from any station to any other station. The stations it can go depends on the numbers labeled on the buttons in the control room. Furthermore, it must refuel after each stop. The time to refuel take one unit of time which is much longer than the time to travel between any pair of stations.
Each space station has a unique number. Assume that there are n stations and they are numbered from 0 to n - 1. The operation of the space ship is very simple. There are only two buttons in a space ship, and each button is marked by a positive integer. Suppose that you are at station s. Pushing the button marked a can take you to station (s + a) mod n, and pushing the other button marked b can take you to station (s+b) mod n. These two numbers marked on the buttons are set at the factory, and they cannot be changed.
Astronauts at station s received a critical mission. To carry out the mission they must go to station t as fast as they can. Since the number of stations is huge, the captain cannot figure out how to get to station t fast. The captain, who is not an expert in programming, has tried a simple program which does a simple search for solutions. The program takes a long time to compute the answer. Please write an efficient program to solve the problem for the captain. In designing the program remember that the captain is left-handed. That is, the captain can push the button labeled a much faster than the button labeled b.