//判断是否是素数
bool is_prime(int num)
{
    if (num < 2)
        return false;
    for (int i = 0; i <= num / i; i++)
    {
        if (num % i == 0)
            return false;
    }
    return true;
}

//判断素数的个数
vector<bool>status;
int cnt;
vector<int>prime;
void cnt_prime(int num)
{
    prime.resize(num + 1, true);
    prime[0] = prime[1] = false;
    for (int i = 2; i <= num; i++)
    {
        if (status[i])
        {
            cnt++;
            prime.push_back(i);
            for (int j = 0; j < prime.size() && prime[j] <= num / i; j++)
            {
                status[prime[j] * i] = false;
                if (i % prime[j] == 0)
                    break;
            }
        }
    }
}

//分解质因数
vector<int>ans;
void prime_divide(int num)
{
    for (int i = 2; i <= num; i++)
    {
        if (num % i == 0)
        {
            ans.push_back(i);
            while (num % i == 0)
            {
                num /= i;
            }
        }
    }
    if (num > 1)
        ans.push_back(num);
}

//分解因数
vector<int>ans;
void get_divisors(int num)
{
    for (int i = 1; i <= num / i; i++)
    {
        if (num % i == 0)
        {
            ans.push_back(i);
            if (i != num / i)
                ans.push_back(num / i);
        }
    }
}

//计算因数个数
unordered_map<int, int>all;
int cnt;
typedef long long ll;
const int mod = 1e9 + 7;
ll count(int num)
{
    for (int i = 2; i <= num / i; i++)
    {
        if (num % i == 0)
        {
            while (num % i == 0)
            {
                all[i]++;
                cnt++;
            }
        }
    }
    if (num > 1)
        all[num]++;
    ll result = 0;
    for (auto i : all)
    {
        result = result * (i.second + 1) % mod;
    }
    return result;
}

//计算因数之和
unordered_map<int, int>all;
int cnt;
typedef long long ll;
const int mod = 1e9 + 7;
ll sum(int num)
{
    for (int i = 2; i <= num / i; i++)
    {
        if (num % i == 0)
        {
            while (num % i == 0)
            {
                all[i]++;
                cnt++;
            }
        }
    }
    if (num > 1)
        all[num]++;
    ll result = 0;
    for (auto cnt : all)
    {
        int p = cnt.first;
        int a = cnt.second;
        ll t = 1;
        for (int i = 0; i < a; i++)
        {
            t = (t * p + 1) % mod;
        }
        result = result * t % mod;
    }
    return result;
}

//欧拉函数,即计算小于n有多少数和n互质
int Euler(int num)
{
    int ans = 0;
    for (int i = 2; i <= num / i; i++)
    {
        if (num % i == 0)
        {
            ans = ans / i * (i - 1); //对应公式ans*(1-1/i)
            while (num % i == 0)
                num /= i;
        }
    }
    if (num > 1)
        ans = ans / num * (num - 1);
    return ans;
}

//线性筛求欧拉函数，即求范围内每个数的欧拉函数值

vector<int>phi;
vector<int>prime;
vector<bool>is_prime;
typedef long long ll;
ll Euler(int num)
{
    phi.resize(num + 1, 1);
    is_prime.resize(num + 1, true);
    for (int i = 2; i <= num; i++)
    {
        if (is_prime[i])
        {
            prime.push_back(i);
            phi[i] = i - 1;
        }
        for (int j = 0; j < prime.size() && prime[j] <= num / i; j++)
        {
            is_prime[prime[j] * i] = false;
            if (i % prime[j] == 0)
            {
                phi[prime[j] * i] = prime[j] * phi[i];
                break;
            }
            phi[prime[j] * i] = (prime[j] - 1) * phi[i];
        }
    }
    ll ans = 0;
    for (auto curr : phi)
        ans += curr;
    return ans-1; //不要index=0
}

//求逆元

//逆元的充要条件是am互质，如果m是质数，则可以用ksp求，否则只能用exgcd求

typedef long long ll;
ll ksp(ll n, ll p, ll mod)
{
    ll ans = 1;
    while (p)
    {
        if (p & 1)
            ans = ans * n % mod;
        p >>= 1;
        n = n * n % mod;
    }
    return ans % mod;
}
ll gcd(ll a, ll b)
{
    return b == 0 ? a : gcd(b, a % b);
}
int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        ll n, p;
        cin >> n >> p;
        if (gcd(n, p) != 1)
            cout << "impossible" << endl;
        else
            cout << ksp(n, p - 2, p)<<endl;
    }
}

//扩展欧几里得

例题：求线性同余方程

typedef long long ll;
int exgcd(int a, int b, int& x, int& y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        int a, b, m;
        cin >> a >> b >> m;
        int x, y = 0;
        int d = exgcd(a, m, x, y);
        if (b % d)
            cout << "impossible" << endl;
        else
            cout << (ll)x * (b / d) % m << endl;;
    }
    return 0;
}