include <iostream>
#include <cmath>
using namespace std;
int main()
{
int arr[100000];
int n;
cin>>n;
long long a,b;
int c;
for(int i = 0; i<n;i++){
cin>>a>>b;
c = pow(b,a-2);
arr[i]= c%a;
}
for(int h = 0;h< n;h++){
cout<<arr[h]<<endl;
return 0;
include <iostream>
#include <cmath>
using namespace std;
int main()
{
int arr[100000];
int n;
cin>>n;
long long a,b;
int c;
for(int i = 0; i<n;i++){
cin>>a>>b;
c = pow(b,a-2);
arr[i]= c%a;
}
for(int h = 0;h< n;h++){
cout<<arr[h]<<endl;
}
return 0;