Обратное число, олимпиадная задача

Помогите, моя программы по мнению тестовой системы Сириуса работает слишком долго. Помогите ускорить мою программу. Вот само задание:

Обратное число

В этой задаче нужно ответить на 1≤t≤10⁵ запросов. Каждый запрос состоит из двух целых чисел 2≤p≤10⁹ и 0<a<p, число p является простым. На каждый запрос нужно вывести в отдельной строке целое число 0<b<p, такое что (a⋅b⁻¹) ⋮ p.

Входные данные:

В первой строке дано целое число t — количество запросов. В следующих t строках даны по два числа p_i и a_i, i=1,... ,t.

Выходные данные:

Выведите: t целых чисел (каждое число в отдельной строке) — ответы на запросы.

Примеры:

Ввод:

4
5 1
5 2
5 3
5 4

Вывод:

1
3
2
4

Ограничения: Время выполнения: 5 секунд

Вот мой код:

b = []
for x in range(int(input())):
    a = list(map(int, input().split()))
    b.append((a[1]) ** (a[0] - 2) % a[0])
print('\n'.join(map(str, b)))