FRAKTAL - konkurs programistyczny

Upraszczanie ułamków

Nie wiem kto i kiedy wprowadził do podręczników nazewnictwo skracania ułamków. Skrócić to można spódnicę. Czyż nie ładniej brzmiałoby upraszczanie ułamków? Niestety sformułowanie przyjęło się i uczniowie chyba będą już tylko skracać ułamki, o ile potrafią :). No właśnie, nie każdy uczeń potrafi w pamięci znaleźć największy wspólny dzielnik dla licznika i mianownika pewnego ułamka. Stąd pani, przy omawianiu zagadnienia, podała prosty przepis na odnalezienie takiego dzielnika. Opiera się on na spostrzeżeniu, że jeśli od większej liczby odejmiemy mniejszą, to mniejsza liczba i otrzymana różnica będą miały taki sam największy wspólny dzielnik jak pierwotne liczby. Postępujemy w ten sposób tak długo, aż różnica będzie równa 0. Ostatnia niezerowa reszta jest największym wspólnym dzielnikiem dwóch liczb - licznika i mianownika.
Sprawdźmy to na przykładzie ułamka 6/24:
24 - 6 = 18
18 - 6 = 12
12 - 6 = 6
6 - 6 = 0
Ostania niezerowa reszta to 6, więc ułamek 6/24 można uprościć przez 6, co daje nam 1/4. W przypadku tego ułamka wykonaliśmy cztery operacje arytmetyczne, które pozwoliły znaleźć wspólny dzielnik. Niestety algorytm ten, oparty na odejmowaniu ma jedną dużą wadę. Czasami liczba odejmowań, jakie trzeba wykonać, jest tak duża, że lepiej pozostawić ułamek w spokoju, nie wspominając o przypadkach, w których jedynym dzielnikiem jest 1 i ułamka nie da się uprościć.
A polecenie dla tego zadania jest takie: wyznacz liczbę operacji, jakie uczeń musi wykonać, aby znaleźć największy wspólny dzielnik metodą podaną wyżej.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 10⁵) oznaczająca liczbę przypadków testowych. Każdy przypadek to ułamek zwykły zapisany w postaci a/b, gdzie (1 ≤ a,b ≤ 10⁹).

Wyjście
Dla każdego ułamka wyznacz liczbę odejmowań, która potrzebna jest do znalezienia największego wspólnego dzielnika licznika i mianownika.

Przykład

Wejście
3
4/6
6/24
1/5

Wyjście
3
4
5