Konkurs 16.10.10 - Liczby

Liczby

Liczby

Limit pamięci: 32MB

Dane jest t trójek liczb naturalnych, gdzie i-tą trójkę oznaczmy jako ai, ci oraz liczbę pi, która jest pierwsza. Dla i-tej trójki chcemy policzyć najmniejsze takie całkowite nieujemne bi, że aibi ≡ ci (mod pi) lub wypisać -1 jeśli takiej liczby nie ma.

Wejście:

Pierwszy wiersz zawiera jedną liczbę naturalną t (1 <= t <= 100) oznaczającą liczbę trójek liczb całkowitych nieujemnych. Każda trójka znajduje się w osobnym wierszu. Oznaczmy trójkę w i+1-szym wierszu po kolei jako ai, ci oraz liczbę pierwszą pi. Każda z liczb w trójce jest mniejsza bądź równa 109.

Wyjście:

Wyjście powinno zawierać t wierszy, w wierszu o numerze i powinna znajdować się najmniejsza taka liczba całkowita nieujemna bi, że aibi ≡ ci (mod pi) lub -1 jeśli takiej liczby nie ma.

Przykład:

Dla wejścia:
5
11 13 19
4 3 5
5 1 11
1 1 2
2 4 5
poprawnym wyjściem jest:
-1
-1
0
0
2