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.|

AL_01_04 - Jasio kryptolog

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*109 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

Dodane przez:Adam Bąk
Data dodania:2012-09-13
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: GOSU
Pochodzenie:ALGOLIGA

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