#include<bits/stdc++.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; }
//   


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; }

ll K,C,T, x, y;

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	cin >> T;
	for(int i=0;i<T;i++){
	cin >> K >> C;
	// need to solve aK == 1 (mod C) or aK+1 = bC
	if (C==1) cout << K+1;
	else if (K==1) cout << 1;
	else if (!canon_egcd(K, C, 1, x, y)) cout << "IMPOSSIBLE";
	else cout << y;
	cout << '\n';
}
}