/*** author: yuji9511 ***/ #include <bits/stdc++.h> using namespace std; using ll = long long; using lpair = pair<ll, ll>; const ll MOD = 1e9+7; const ll INF = 1e18; #define rep(i,m,n) for(ll i=(m);i<(n);i++) #define rrep(i,m,n) for(ll i=(m);i>=(n);i--) #define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];}; void print() {} template <class H,class... T> void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);} vector<ll> sieve(ll n){ //エラトステネス vector<bool> is_prime(n+1); vector<ll> prime; rep(i,0,n+1) is_prime[i] = true; is_prime[0] = is_prime[1] = false; rep(i,2,n+1){ if(is_prime[i]){ prime.push_back(i); for(int j = 2 * i; j <= n; j += i) is_prime[j] = false; } } return prime; rep(i,0,(1<<60)){ print(i); } } ll power(ll x, ll n, ll M){ if(n == 0) return 1LL; ll res = power(x * x % M, n/2, M); if(n % 2 == 1) res = res * x % M; return res; } vector<ll> primes = sieve(5000000); void solve(){ map<int,bool> mp; for(auto &e: primes) mp[e] = true; ll T; cin >> T; while(T--){ ll A,P; cin >> A >> P; if(not mp[P]){ print(-1); }else{ if(A % P == 0){ print(0); }else{ print(1); } } } } int main(){ cin.tie(0); ios::sync_with_stdio(false); solve(); }