intquick_power(int a, int b, int p) { int res = 1; while (b) { if (b&1) res = (LL)res * a % p; a = (LL)a*a % p; b >>= 1; } return res % p; }
intmain() { int n; cin >> n; while (n -- ) { int a, p; cin >> a >> p; int x = quick_power(a, p-2, p); //直接求出逆元的值! if (a%p) cout << x << endl; elseputs("impossible"); } return0; }