/**
Abir3014
**/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<pair<ll, ll>> vii;
typedef multiset<pair<ll, ll>> msii;
typedef multiset<ll> msi;
typedef set<pair<ll, ll>> sii;
typedef set<ll> si;
typedef map<ll, ll> mii;
#define recap(i,k,n) for(int i = k; i>=n; i--)
#define rep(i,k,n) for(int i=k; i<n; i++)
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define for1(x, a, b) for(x=a; x<b; x++)
#define for2(x, a, b) for(x=a, x>=b; x--)
#define endl "\n"
#define all(x) x.begin(), x.end()
#define mp make_pair
#define read freopen("input.txt","r",stdin)
#define write freopen("output.txt","w",stdout)
#define pb push_back
#define ff first
#define ss second
#define bb begin
#define mem(arr, x) memset(arr, x, sizeof(arr));
#define arr_ub(arr, n, x) upper_bound(arr, arr+n, x)-arr
#define arr_lb(arr, n, x) lower_bound(arr, arr+n, x)-arr
#define u_p(v, x) upper_bound(v.begin(), v.end(), x)-v.begin()
#define l_b(v, x) lower_bound(v.begin(), v.end(), x)-v.begin()
const ll sz=1e6+123;
#define INF 1000000000000000007
#define MOD 1000000007
#define stringLen 18446744073709551620
#define pi 3.1415926536
inline void normal(ll &a) { a %= MOD; (a < 0) && (a += MOD); }
inline ll modMul(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a*b)%MOD; }
inline ll modAdd(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); return (a+b)%MOD; }
inline ll modSub(ll a, ll b) { a %= MOD, b %= MOD; normal(a), normal(b); a -= b; normal(a); return a; }
inline ll modPow(ll b, ll p) { ll r = 1; while(p) { if(p&1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
inline ll modInverse(ll a) { return modPow(a, MOD-2); }
inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }
//vi divisorList[sz];
//ll divisorNumber[sz];
//void findDivisor(ll n){
// for(ll i=1; i<=n; i++){
// for(ll j=i; j<=n; j+=i){
// divisorList[j].pb(i);
// divisorNumber[j]++;
// }
// }
//}
//bool isPalindrome(string s){ll i=0,j=s.size()-1;for(i,j;i<=j;i++,j--){if(s[i]!=s[j]) return 0;}return 1;}
ll gcd(ll a, ll b){return b==0? a: gcd(b, a%b);}
//// lcm * gcd = a*b
//ll lcm(ll a, ll b){if(a>b)swap(a, b);return a*(b/gcd(a, b));}
//bool isPalindrome(string s){ ll i=0,j=s.size()-1;for(i,j;i<=j;i++,j--){if(s[i]!=s[j]) return 0;} return 1;}
//bool isPowerofTwo(ll n){return (n && !(n&(n-1)));}
//int count_one(ll n){int count=0;while(n){n &= (n-1);count++;}return count;}
//string binRep(ll n){string s="";int f = 0;while(n>0){if(n%2){f=1;s+='1';}else s+='0';n/=2;}if(s.empty())return "0";else return s;}
//int ctz(ll n){return __builtin_ctzll(n);}
//int clz(ll n){return __builtin_clzll(n);}
//int bitCount(ll n){return __builtin_popcountll(n);}
//bitset<sz>is_prime;
//vi prime;
//
//void primeGen(int n){
// for(int i=3; i<=n; i+=2)is_prime[i]=1;
// int nn = sqrt(n)+1;
// for(ll i=3; i<nn; i+=2){
// if(is_prime[i]==0)continue;
// for(int j=i*i; j<=n; j+=(i+i)){
// is_prime[j]=0;
// }
// }
// is_prime[2]=1;
// prime.pb(2);
// for(int i=3; i<=n; i+=2){
// if(is_prime[i])prime.pb(i);
// }
//
//}
//
//vector<long long>primeDivisors[sz];
//long long primeDivisorNumbers[sz];
//void findPrimeDivisors(long long n){
// for(auto u:prime){
// for(long long i = u; i<=n; i+=u){
// primeDivisors[i].push_back(u);
// primeDivisorNumbers[i]++;
// }
// }
//}
//
//
//vector<long long>factorization(long long n){
// //O(sqrt(n)/ln(sqrt(n)) + log2 n)
// vector<long long>factors;
// for(auto u:prime){
// if(1LL*u*u > n) break;
// if(n%u==0){
// // factors.push_back(u);//for generating unique factors keep this line here
// while(n%(u)==0){
// //factors.push_back(u);//for generating all factors keep this line here
// n/=(u);
// }
// }
// }
// if(n>1)factors.push_back(n);
// return factors;
//}
//
//int NOD(long long n){
// int res=1;
// for(auto u:prime){
// if(1LL*u*u > n)break;
// if(n%u==0){
// int count=1;
// while(n%u==0){
// n/=u;
// count++;
// }
// res *= count;
// }
// }
// if(n>1)res*=2;
// return res;
//}
ll test=0;
void solve(){
int a, b;
cin>>a>>b;
if(gcd(a, b)>1){
cout << 0 << endl;
}
else if((a%2==1 && b%2==0)||(a%2==0 && b%2==1)){
cout << 1 << endl;
}
else if(a%2==1 && b%2==1){
int x = min(a, b);
int y = max(a, b);
if(x==1){
cout << 2 << endl;
}
else{
int xxx = x-y%x;
cout << min(2, xxx) << endl;
}
}
//cout<<"Case "<<++test<": "<<ans<<endl;
//cout<<"Case #"<<++Case<<": ";
}
int main(){
boost;
//read; write;
int t; cin>>t; for(int i=1; i<=t; i++)
solve();
return 0;
}
LyoqCkFiaXIzMDE0CioqLwoKI2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnR5cGVkZWYgbG9uZyBsb25nIGxsOwoKdHlwZWRlZiAgIHZlY3RvcjxsbD4gIHZpOwp0eXBlZGVmICAgdmVjdG9yPHBhaXI8bGwsIGxsPj4gdmlpOwp0eXBlZGVmICAgbXVsdGlzZXQ8cGFpcjxsbCwgbGw+PiBtc2lpOwp0eXBlZGVmICAgbXVsdGlzZXQ8bGw+IG1zaTsKdHlwZWRlZiAgIHNldDxwYWlyPGxsLCBsbD4+IHNpaTsKdHlwZWRlZiAgIHNldDxsbD4gc2k7CnR5cGVkZWYgICBtYXA8bGwsIGxsPiBtaWk7CgoKI2RlZmluZSByZWNhcChpLGssbikgIGZvcihpbnQgaSA9IGs7IGk+PW47IGktLSkKI2RlZmluZSByZXAoaSxrLG4pICAgIGZvcihpbnQgaT1rOyBpPG47IGkrKykKI2RlZmluZSBib29zdCAJaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbygwKTtjaW4udGllKDApO2NvdXQudGllKDApOwojZGVmaW5lIGZvcjEoeCwgYSwgYikgIGZvcih4PWE7IHg8YjsgeCsrKQojZGVmaW5lIGZvcjIoeCwgYSwgYikgIGZvcih4PWEsIHg+PWI7IHgtLSkKI2RlZmluZSBlbmRsIAkiXG4iCiNkZWZpbmUgYWxsKHgpICB4LmJlZ2luKCksIHguZW5kKCkKI2RlZmluZSBtcCAgICAgIG1ha2VfcGFpcgojZGVmaW5lIHJlYWQgICAgZnJlb3BlbigiaW5wdXQudHh0IiwiciIsc3RkaW4pCiNkZWZpbmUgd3JpdGUgICBmcmVvcGVuKCJvdXRwdXQudHh0IiwidyIsc3Rkb3V0KQojZGVmaW5lIHBiICAgICAgcHVzaF9iYWNrCiNkZWZpbmUgZmYgICAgICBmaXJzdAojZGVmaW5lIHNzICAgICAgc2Vjb25kCiNkZWZpbmUgYmIgICAgICBiZWdpbgojZGVmaW5lIG1lbShhcnIsIHgpIG1lbXNldChhcnIsIHgsIHNpemVvZihhcnIpKTsKI2RlZmluZSBhcnJfdWIoYXJyLCBuLCB4KSB1cHBlcl9ib3VuZChhcnIsIGFycituLCB4KS1hcnIKI2RlZmluZSBhcnJfbGIoYXJyLCBuLCB4KSBsb3dlcl9ib3VuZChhcnIsIGFycituLCB4KS1hcnIKI2RlZmluZSB1X3AodiwgeCkgdXBwZXJfYm91bmQodi5iZWdpbigpLCB2LmVuZCgpLCB4KS12LmJlZ2luKCkKI2RlZmluZSBsX2IodiwgeCkgbG93ZXJfYm91bmQodi5iZWdpbigpLCB2LmVuZCgpLCB4KS12LmJlZ2luKCkKCgpjb25zdCBsbCBzej0xZTYrMTIzOwojZGVmaW5lIElORiAxMDAwMDAwMDAwMDAwMDAwMDA3CiNkZWZpbmUgTU9EIDEwMDAwMDAwMDcKI2RlZmluZSBzdHJpbmdMZW4gMTg0NDY3NDQwNzM3MDk1NTE2MjAKI2RlZmluZSBwaSAzLjE0MTU5MjY1MzYKCmlubGluZSB2b2lkIG5vcm1hbChsbCAmYSkgeyBhICU9IE1PRDsgKGEgPCAwKSAmJiAoYSArPSBNT0QpOyB9CmlubGluZSBsbCBtb2RNdWwobGwgYSwgbGwgYikgeyBhICU9IE1PRCwgYiAlPSBNT0Q7IG5vcm1hbChhKSwgbm9ybWFsKGIpOyByZXR1cm4gKGEqYiklTU9EOyB9CmlubGluZSBsbCBtb2RBZGQobGwgYSwgbGwgYikgeyBhICU9IE1PRCwgYiAlPSBNT0Q7IG5vcm1hbChhKSwgbm9ybWFsKGIpOyByZXR1cm4gKGErYiklTU9EOyB9CmlubGluZSBsbCBtb2RTdWIobGwgYSwgbGwgYikgeyBhICU9IE1PRCwgYiAlPSBNT0Q7IG5vcm1hbChhKSwgbm9ybWFsKGIpOyBhIC09IGI7IG5vcm1hbChhKTsgcmV0dXJuIGE7IH0KaW5saW5lIGxsIG1vZFBvdyhsbCBiLCBsbCBwKSB7IGxsIHIgPSAxOyB3aGlsZShwKSB7IGlmKHAmMSkgciA9IG1vZE11bChyLCBiKTsgYiA9IG1vZE11bChiLCBiKTsgcCA+Pj0gMTsgfSByZXR1cm4gcjsgfQppbmxpbmUgbGwgbW9kSW52ZXJzZShsbCBhKSB7IHJldHVybiBtb2RQb3coYSwgTU9ELTIpOyB9CmlubGluZSBsbCBtb2REaXYobGwgYSwgbGwgYikgeyByZXR1cm4gbW9kTXVsKGEsIG1vZEludmVyc2UoYikpOyB9CgoKLy92aSBkaXZpc29yTGlzdFtzel07Ci8vbGwgZGl2aXNvck51bWJlcltzel07Ci8vdm9pZCBmaW5kRGl2aXNvcihsbCBuKXsKLy8JICBmb3IobGwgaT0xOyBpPD1uOyBpKyspewovLwkJCWZvcihsbCBqPWk7IGo8PW47IGorPWkpewovLwkJCQkgZGl2aXNvckxpc3Rbal0ucGIoaSk7Ci8vCQkgICAgIAkgZGl2aXNvck51bWJlcltqXSsrOwovLwkJCX0KLy8JICB9Ci8vfQoKLy9ib29sIGlzUGFsaW5kcm9tZShzdHJpbmcgcyl7bGwgaT0wLGo9cy5zaXplKCktMTtmb3IoaSxqO2k8PWo7aSsrLGotLSl7aWYoc1tpXSE9c1tqXSkgcmV0dXJuIDA7fXJldHVybiAxO30KbGwgZ2NkKGxsIGEsIGxsICBiKXtyZXR1cm4gYj09MD8gYTogZ2NkKGIsIGElYik7fQovLy8vIGxjbSAqIGdjZCA9IGEqYgovL2xsIGxjbShsbCBhLCBsbCBiKXtpZihhPmIpc3dhcChhLCBiKTtyZXR1cm4gYSooYi9nY2QoYSwgYikpO30KLy9ib29sIGlzUGFsaW5kcm9tZShzdHJpbmcgcyl7IGxsIGk9MCxqPXMuc2l6ZSgpLTE7Zm9yKGksajtpPD1qO2krKyxqLS0pe2lmKHNbaV0hPXNbal0pIHJldHVybiAwO30gcmV0dXJuIDE7fQovL2Jvb2wgaXNQb3dlcm9mVHdvKGxsIG4pe3JldHVybiAobiAmJiAhKG4mKG4tMSkpKTt9Ci8vaW50IGNvdW50X29uZShsbCBuKXtpbnQgY291bnQ9MDt3aGlsZShuKXtuICY9IChuLTEpO2NvdW50Kys7fXJldHVybiBjb3VudDt9Ci8vc3RyaW5nIGJpblJlcChsbCBuKXtzdHJpbmcgcz0iIjtpbnQgZiA9IDA7d2hpbGUobj4wKXtpZihuJTIpe2Y9MTtzKz0nMSc7fWVsc2Ugcys9JzAnO24vPTI7fWlmKHMuZW1wdHkoKSlyZXR1cm4gIjAiO2Vsc2UgcmV0dXJuIHM7fQovL2ludCBjdHoobGwgbil7cmV0dXJuIF9fYnVpbHRpbl9jdHpsbChuKTt9Ci8vaW50IGNseihsbCBuKXtyZXR1cm4gX19idWlsdGluX2NsemxsKG4pO30KLy9pbnQgYml0Q291bnQobGwgbil7cmV0dXJuIF9fYnVpbHRpbl9wb3Bjb3VudGxsKG4pO30KCi8vYml0c2V0PHN6PmlzX3ByaW1lOwovL3ZpIHByaW1lOwovLwovL3ZvaWQgcHJpbWVHZW4oaW50IG4pewovLyAgICAgZm9yKGludCBpPTM7IGk8PW47IGkrPTIpaXNfcHJpbWVbaV09MTsKLy8gICAgIGludCBubiA9IHNxcnQobikrMTsKLy8gICAgIGZvcihsbCBpPTM7IGk8bm47IGkrPTIpewovLwkJICAgICBpZihpc19wcmltZVtpXT09MCljb250aW51ZTsKLy8JCQlmb3IoaW50IGo9aSppOyBqPD1uOyBqKz0oaStpKSl7Ci8vCQkJCWlzX3ByaW1lW2pdPTA7Ci8vCQkJfQovLyAgICAgfQovLyAgICAgaXNfcHJpbWVbMl09MTsKLy8gICAgIHByaW1lLnBiKDIpOwovLyAgICAgZm9yKGludCBpPTM7IGk8PW47IGkrPTIpewovLwkgICAgICBpZihpc19wcmltZVtpXSlwcmltZS5wYihpKTsKLy8gICAgIH0KLy8KLy99Ci8vCi8vdmVjdG9yPGxvbmcgbG9uZz5wcmltZURpdmlzb3JzW3N6XTsKLy9sb25nIGxvbmcgcHJpbWVEaXZpc29yTnVtYmVyc1tzel07Ci8vdm9pZCBmaW5kUHJpbWVEaXZpc29ycyhsb25nIGxvbmcgbil7Ci8vCWZvcihhdXRvIHU6cHJpbWUpewovLwkJZm9yKGxvbmcgbG9uZyBpID0gdTsgaTw9bjsgaSs9dSl7Ci8vCQkJcHJpbWVEaXZpc29yc1tpXS5wdXNoX2JhY2sodSk7Ci8vCQkJcHJpbWVEaXZpc29yTnVtYmVyc1tpXSsrOwovLwkJfQovLwl9Ci8vfQovLwovLwovL3ZlY3Rvcjxsb25nIGxvbmc+ZmFjdG9yaXphdGlvbihsb25nIGxvbmcgbil7Ci8vCS8vTyhzcXJ0KG4pL2xuKHNxcnQobikpICsgbG9nMiBuKQovLwl2ZWN0b3I8bG9uZyBsb25nPmZhY3RvcnM7Ci8vCWZvcihhdXRvIHU6cHJpbWUpewovLwkJaWYoMUxMKnUqdSA+IG4pIGJyZWFrOwovLwkJaWYobiV1PT0wKXsKLy8JCS8vCWZhY3RvcnMucHVzaF9iYWNrKHUpOy8vZm9yIGdlbmVyYXRpbmcgdW5pcXVlIGZhY3RvcnMga2VlcCB0aGlzIGxpbmUgaGVyZQovLwkJCXdoaWxlKG4lKHUpPT0wKXsKLy8JCQkJLy9mYWN0b3JzLnB1c2hfYmFjayh1KTsvL2ZvciBnZW5lcmF0aW5nIGFsbCBmYWN0b3JzIGtlZXAgdGhpcyBsaW5lIGhlcmUKLy8JCQkJbi89KHUpOwovLwkJCX0KLy8JCX0KLy8JfQovLwlpZihuPjEpZmFjdG9ycy5wdXNoX2JhY2sobik7Ci8vCXJldHVybiBmYWN0b3JzOwovL30KLy8KLy9pbnQgTk9EKGxvbmcgbG9uZyBuKXsKLy8JaW50IHJlcz0xOwovLwlmb3IoYXV0byB1OnByaW1lKXsKLy8JCWlmKDFMTCp1KnUgPiBuKWJyZWFrOwovLwkJaWYobiV1PT0wKXsKLy8JCSAgICAgIGludCBjb3VudD0xOwovLwkJCXdoaWxlKG4ldT09MCl7Ci8vCQkJCW4vPXU7Ci8vCQkJCWNvdW50Kys7Ci8vCQkJfQovLwkJCXJlcyAqPSBjb3VudDsKLy8JCX0KLy8JfQovLwlpZihuPjEpcmVzKj0yOwovLwlyZXR1cm4gcmVzOwovL30KCmxsIHRlc3Q9MDsKdm9pZCBzb2x2ZSgpewogICAgIGludCBhLCBiOwogICAgIGNpbj4+YT4+YjsKICAgICAKICAgICBpZihnY2QoYSwgYik+MSl7CiAgICAgICAgICBjb3V0IDw8IDAgPDwgZW5kbDsKICAgICB9CiAgICAgZWxzZSBpZigoYSUyPT0xICYmIGIlMj09MCl8fChhJTI9PTAgJiYgYiUyPT0xKSl7CiAgICAgICAgICBjb3V0IDw8IDEgPDwgZW5kbDsKICAgICB9CiAgICAgZWxzZSBpZihhJTI9PTEgJiYgYiUyPT0xKXsKICAgICAgICAgIGludCB4ID0gbWluKGEsIGIpOwogICAgICAgICAgaW50IHkgPSBtYXgoYSwgYik7CiAgICAgICAgICBpZih4PT0xKXsKICAgICAgICAgICAgICAgY291dCA8PCAyIDw8IGVuZGw7CiAgICAgICAgICB9CiAgICAgICAgICBlbHNlewogICAgICAgICAgICAgICBpbnQgeHh4ID0geC15JXg7CiAgICAgICAgICAgICAgIGNvdXQgPDwgbWluKDIsIHh4eCkgPDwgZW5kbDsKICAgICAgICAgIH0KICAgICB9CiAgICAgCiAgICAgIC8vY291dDw8IkNhc2UgIjw8Kyt0ZXN0PCI6ICI8PGFuczw8ZW5kbDsKICAgICAgLy9jb3V0PDwiQ2FzZSAjIjw8KytDYXNlPDwiOiAiOwoKfQppbnQgbWFpbigpewoJYm9vc3Q7CgkvL3JlYWQ7IHdyaXRlOwoJaW50IHQ7IGNpbj4+dDsgZm9yKGludCBpPTE7IGk8PXQ7IGkrKykKCXNvbHZlKCk7CgoKCXJldHVybiAwOwp9CgoKCgo=