как сократить время программы

нужно сократить время программы до 5 секунд

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

Обратное число В этой задаче нужно ответить на 1 ≤ t ≤ 10^5 запросов. Каждый запрос состоит из двух целых чисел 2 ≤ p ≤ 10^9 и 0 < a < p, число p является простым. На каждый запрос нужно вывести в отдельной строке целое число 0 < b < p такое, что (ab − 1) ⋮ p.

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

4
5 1
5 2
5 3
5 4

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

1
3
2
4

Задачу понял отлично, но как сократить время выполнения не имею представления.