Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_06_13 - Upraszczanie ułamków

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 ≤ 105) oznaczająca liczbę przypadków testowych. Każdy przypadek to ułamek zwykły zapisany w postaci a/b, gdzie (1 ≤ a,b ≤ 109).

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


Dodane przez:Mariusz Śliwiński
Data dodania:2016-10-17
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM32-GCC ASM64 COBOL D-DMD D-CLANG ELIXIR FANTOM GOSU GRV JS-MONKEY NIM OBJC OBJC-CLANG PICO RUST CHICKEN SCM qobi VB.NET

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.