/*
快速幂求逆元：
    快速幂的逆元==在取模的条件下的逆元
    费马定理：b * x = 1（mod p素数）
    快速幂的逆元存在性：b与p互质
*/

/*
I n : (ai, pi)
模运算下的逆元，1～p-1
O 存在逆元则输出否则输出“impossible”

I
3
4 3
8 5
6 3

O
1
2
impossible

*/

#include <iostream>
#include <algorithm>

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;
        a = a * (LL)a % p;
        b >>= 1;
    }
    return res;
}


int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, p;
        scanf("%d%d", &a, &p);
        if (a % p == 0) puts("impossible");
        // 使用费马定理直接推导快速幂的逆元的公式：b * x = 1(mod p)
        else printf("%lld\n", qmi(a, p - 2, p));
    }

    return 0;
}