#include <bits/stdc++.h>
using namespace std;
#define int long long
bool Isprime(int N){
  bool ok = (N != 1);
  for(int i=2;i*i<=N;i++){
    if(N%i == 0) ok = false;
  }
  return ok;
}
signed main(){
  int T;
  cin>>T;
  for(int i=0;i<T;i++){
      int A,P;
      cin>>A>>P;
      if(!Isprime(P)){
          cout<<-1<<endl;
          continue;
      }
      if(A%P == 0) cout<<0<<endl;
      else cout<<1<<endl;
  }
}