Dla każdej podanej pary (x,p) znajdź odwrotność x modulo p. W tym zadaniu p jest na pewno pierwsze.
W pierwszej linii znajduje się ilość testów T. Każdy test jest opisywany przez parę liczb (x,p), których znaczenie jest jak wyżej. 1 ≤ x < p, 2 ≤ p ≤ 2*10^9
Wypisz T odpowiednich liczb.
Dla danych wejściowych
3
1 2
3 7
5 23
poprawną odpowiedzią jest
1
5
14