#include using namespace std; typedef long long ll; typedef vector vll; typedef vector vvll; typedef pair P; typedef vector

vp; typedef vector vs; typedef vector vb; const ll mod=1e9+7; const ll inf=1e16; #define rep(i,m,n) for(ll i=m;i=n;i--) #define fi first #define se second #define chmax(x,y) x=max(x,y) #define chmin(x,y) x=min(x,y) #define eb(x) emplace_back(x) #define pb(x) pop_back(x) #define all(x) x.begin(),x.end() #define allr(x) x.rbegin(),x.rend() #define sum(x) accumulate(all(x),0) #define pc(x) __builtin_popcount(x) #define gll greater() void solve(){ vll prime(5000005,1); prime[0]=0; prime[1]=0; rep(i,2,5000005){ if(!prime[i]) continue; for(ll j=2*i;j<5000005;j+=i) prime[j]=0; } ll t; cin >> t; while(t--){ ll a,p; cin >> a >> p; if(prime[p]) cout << ((a%p)?1:0) << endl; else cout << -1 << endl; } } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); solve(); }