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.