Помогите решить Задачу Обратное число на с++. Написал сам код но он не проходит тесты.

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

В следующих t
строках даны по два числа pi
и ai
, i=1,…,t
.
Выходные данные
Выведите t
целых чисел (каждое число в отдельной строке) — ответы на запросы.

Мой код:
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{

int n;
cin >> n;
int p, a;
for(int i = 0; i < n; i++){
cin >> p >> a;
for(int b = 1; b < p; b++){
if(((b*a)-1)%p==0){
cout << b << endl;
break;}
}
}
}