证明：

证：$a/b ≡ a * x (mod\ m)$

两边同乘 b 得：$a ≡ a * b * x (mod\ m)$

消去 a 得：$b * x (mod\ m) ≡ 1$
即： $b * x ≡ 1 (mod\ m)$

有费马小定理：当 p 为质数时，b 不为 p 的倍数时，$b^{p - 1} ≡ 1 (mod\ p)$
提出一个 b 得：$b* b^{p - 2} ≡ 1 (mod\ p)$

对于上述定理，即当 b 不为 p 的倍数时， $x ≡ b^{m - 2}$，满足$a/b ≡ a * x (mod\ m)$

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

    return res;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int a, b, p;
        scanf("%d%d", &a, &p);

        if(a % p) printf("%lld\n", qmi(a, p - 2, p));
        else printf("impossible\n");
    }
    return 0;
}