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.
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 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.
[Zgłoś rozwiązanie] [Moje zgłoszenia]