#include <bits/stdtr1c++.h>
using namespace std;

typedef long long ll;

////////////////////////////////////////////////////////////////////////////////
// Extended GCD
////////////////////////////////////////////////////////////////////////////////
// Find x,y such that ax + by = d = gcd(a,b)
// * a^-1 (mod m): if (egcd(a,m,x,y) == 1) return (x+m)%m; else ERROR;
ll egcd(ll a, ll b, ll& x, ll &y) {
  if (!b) {x = 1; y = 0; return a;}//to ensure d>=0: x=sgn(a);y=0;return abs(a);
  ll d = egcd(b, a%b, y, x); y -= x * (a/b); return d; }
////////////////////////////////////////////////////////////////////////////////
// Extended GCD in canonical form
////////////////////////////////////////////////////////////////////////////////
// Assuming a != 0, find smallest y >= 0 such that ax + by = c (if possible)
bool canon_egcd(ll a, ll b, ll c, ll& x, ll& y) {
  ll d = egcd(a, b, x, y), z = abs(a/d); if (c%d) return false;
  y = (y*(c/d)%z + z)%z, x = (c - b*y)/a; return true; }

int main() {
  ios::sync_with_stdio(0);
  int t; cin >> t;
  while (t--) {
    ll a, b, x, y;
    cin >> a >> b;
    if (b == 1)
      cout << a+1 << "\n";
    else if (a == 1)
      cout << 1 << "\n";
    else if (canon_egcd(a,b,1,x,y) && y <= 1000000000)
      cout << y << "\n";
    else
      cout << "IMPOSSIBLE\n";
  }
  return 0;
}