#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;

int quickmi(LL a, int b, int p) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    while (n -- ) {
        int a, p;
        cin >> a >> p;
        if (a % p != 0 && p - 2 >= 0) cout << quickmi(a, p - 2, p) << endl;
        else cout << "impossible" << endl;
    }
    return 0;
}