/**
 * Sergey Kopeliovich (burunduk30@gmail.com)
 */

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(), (a).end()

#define Assert(a) assert(a)

typedef long long ll;

inline bool Eq( ll a, ll b, int mod ) { return (a - b) % mod == 0; }
inline int Add( int a, int b, int mod ) { a += b; return a >= mod ? a - mod : a; }
inline int Sub( int a, int b, int mod ) { a -= b; return a < 0 ? a + mod : a; }
inline int Mul( int x, int y, int mod ) { return ((ll)x * y) % mod; }
inline int Sqr( int a, int mod ) { return Mul(a, a, mod); }

int Pow( int x, ll n, int mod ) {
	if (n == 0)
		return mod > 1 ? 1 : 0;
	int y = Pow(x, n / 2, mod);
	y = Mul(y, y, mod);
	return (n & 1) ? Mul(y, x, mod) : y;
}

int Euclid( int a, int b, int &x, int &y ) { // a * x + b * y = gcd
	if (b == 0) {
		x = 1, y = 0;
		return a;
	}
	int k = a / b, gcd = Euclid(b, a % b, x, y);
	swap(x, y), y -= k * x;
	Assert(abs(x) <= b && abs(y) <= a);
	Assert(a * x + b * y == gcd);
	return gcd;
}

int Inv( int a, int m ) { // x * a + y * m == 1
	int x, y, gcd = Euclid(m, a, y, x);
	Assert(gcd == 1);
	Assert(Eq((ll)x * a, 1, m));
	return x < 0 ? x + m : x;
}

int Div( int a, int b, int p ) {
	return Mul(a, Inv(b, p), p);
}

int notRootP(int p) {
  int x = 2;
  while (Pow(x, (p - 1) / 2, p) == 1)
    x++, assert(x < p);
  return x;
}

bool hasRootP(int a, int p) {
  return a == 0 || Pow(a, (p - 1) / 2, p) == 1;
}

// x^2 = a(mod p), Time = O(log)
// return value for no roots: -1
int getRootP(int a, int p) {
  if (p == 2) return a;
  if (a == 0) return 0;
  if (!hasRootP(a, p)) return -1;
  printf("%d %d\n", a, p);

  int deg = (p - 1) / 2;
  while (1) {
    int ru = 0, rv = 1;
    int n = deg, u = 1, v = rand() % p, tu, tv;
    while (n) {
      #define MUL(ru, rv, u, v) \
        tu = Mul(rv, u, p) + Mul(ru, v, p), \
        tv = Mul(Mul(ru, u, p), a, p) + Mul(rv, v, p), \
        ru = tu, rv = tv;
      if (n & 1)
        MUL(ru, rv, u, v)
      MUL(u, v, u, v)
      n >>= 1;
    }
    ru %= p, rv = (rv + p - 1) % p;
    if (ru != 0) {
      int x = Div(p - rv, ru, p);
      if (Eq(Sqr(x, p), a, p))
        return x;
    }
  }
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0);
	int n, a, p;
	cin >> n;
	while (n--) {
		cin >> a >> p;
		int root = getRootP(a, p);
		if (root == -1)
			cout << "IMPOSSIBLE\n";
		else
			cout << root << "\n";
	}
}