费马小定理：当P为质数时，b在mod P 的逆元为：b^p-2

若b是p的倍数时不存在逆元，b与p互质才存在逆元

C++ 代码

//当两个数互质时才存在逆元：（a，b）= 1

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

//a要开LL，不然过程中会爆int
LL quick_mi(LL a, int k, int q)
{
    LL res = 1;
    while(k)
    {
        if(k & 1)
            res = res * a % q;
        k >>= 1;
        a = a * a % q;
    }

    return res;
}


int main()
{

    int n, b, p;
    scanf("%d", &n);
    while(n--)
    {
        scanf("%d%d", &b, &p);

        //如果b是p的倍数，应为p为质数，那么b^p-2也是p的倍数，不存在逆元
        if(b % p == 0)
            puts("impossible");
        else
            printf("%lld\n", quick_mi(b, p-2, p));

    }

    return 0;
}