Zapytania
Limit pamięci: 32 MB
Kryptograf Bajtazar pracuje nad złamaniem szyfru ABB
(Agencji Bezpieczeństwa Bajtocji).
Doszedł już do tego, że przy odszyfrowywaniu wiadomości będzie musiał
wielokrotnie odpowiadać na zapytania postaci:
"dla danych liczb naturalnych
,
i
,
ile jest takich par liczb naturalnych
, że:
-
,
-
,
-
, gdzie
to największy wspólny
dzielnik liczb
i
".
Bajtazar chciałby zautomatyzować swoją pracę, więc poprosił Cię o pomoc.
Zadanie
Napisz program, który:
-
wyczyta ze standardowego wejścia listę zapytań, na które musi
odpowiedzieć Bajtazar,
-
wyznaczy odpowiedzi na te zapytania,
-
wypisze wynik na standardowe wyjście.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną dodatnią
liczbę całkowitą
(
), oznaczającą liczbę zapytań Bajtazara.
Każdy z kolejnych
wierszy zawiera po trzy liczby całkowite
,
i
(
), pooddzielane
pojedynczymi odstępami.
Każda taka trójka reprezentuje jedno zapytanie.
Wyjście
Twój program powinien wypisać na standardowe wyjście
wierszy.
Wiersz
powinien zawierać jedną liczbę całkowitą:
odpowiedź na
-te zapytanie z wejścia.
Przykład
Dla danych wejściowych:
2
4 5 2
6 4 3
poprawną odpowiedzią jest:
3
2
Pary uzyskane w pierwszym zapytaniu to:
,
i
,
a w drugim:
i
.
Autor zadania: Jakub Radoszewski.