/* ===== 解题思路 =====
1. p是质数，当 a 和 p 互质时，a 模 p 的乘法逆元是 a^(p-2) % p （在0~p-1上的逆元）
2. 用快速幂求 a^(p-2) % p
*/

#include <iostream>

using namespace std;

int fastpow(int a, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * 1ll * a % p;
        a = a * 1ll * a % p;
        k >>= 1;
    }
    return res;
}

int main() {
    int n;
    cin >> n;

    while (n --) {
        int a, p;
        cin >> a >> p;
        if (a % p != 0) { // a 和 p 互质
            cout << fastpow(a, p - 2, p) << endl;
        } else {
            cout << "impossible" << endl;
        }
    }

    return 0;
}