//这里填你的代码^^
//注意代码要放在两组三个点之间，才可以正确显示代码高亮哦~
#include<iostream>

using namespace std;

typedef long long LL;

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


int main()
{
    int n;
    scanf("%d", &n);
    while (n--)
    {
        int a, p;
        // 注意输入输出
        scanf("%d%d", &a, &p);
        if (a % p == 0) cout << "impossible" << endl;
        else printf("%lld\n", qmi(a, p - 2, p));
    }
    return 0;
}