AlgoLiga 2018

Jasio wymyślił sposób na komunikowanie się ze znajomymi z klasy podczas lekcji. Pisanie zwykłych liścików to przeżytek. Mogą zostać przechwycone i użyte przeciwko autorowi. Użyje więc algorytmu RSA! Proste i szybkie, a w dodatku przechwyconej bezsensownej wiadomości zawsze można się wyprzeć. Pojawił się tylko jeden problem. Jasio zauważył, że czasem komunikaty po zaszyfrowaniu nie zmieniają swojej wartości. Chciałby wybrać taki klucz publiczny, aby było ich jak najmniej. Ma już kilku kandydatów na poprawne klucze publiczne, ale nie wie który z nich byłby najlepszy. Twoim zadaniem jest pomóc Jasiowi.

Wejście

Wejście zaczyna się od liczby przypadków testowych t <= 100. Każdy przypadek testowy składa się z trzech liczb kolejno: p, q, e, gdzie p, q to różne liczby pierwsze, pq <= 4*10⁹ oraz 1 < e < φ(pq) jest względnie pierwsze z φ(pq). Para (pq, e) stanowi klucz publiczny o który pyta Jasio.

Wyjście

Dla każdego klucza publicznego należy wypisać w oddzielnej linii ilość komunikatów ze zbioru {0, ..., pq-1}, które po zaszyfrowaniu wyglądają tak samo jak przed.

Przykład

Wejście:
1
71 103 19

Wyjście:
21