#include <iostream>
#include <string>
#define ll long long
using namespace std;
ll ss(int a,int b, int c){
ll res = 1;
while(b){
if(b & 1) res = res * a % c;
a = a * (ll) a % c;
b >>= 1;
}
return res;
}
void solve(){
int a,b;
scanf("%d%d",&a,&b);
if(a % b == 0) printf("impossible\n");
else printf("%lld\n",ss(a,b - 2,b));
return;
}
int main(){
int t;
scanf("%d",&t);
while(t --)
solve();
return 0;
}
送你个板子:
template <class T> T quick_power(T a, T b, auto mod) { if (b == 0) return 1 % mod; auto ns = quick_power(a, b >> 1, mod); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns; }
谢谢大佬orz