#include using namespace std; using ll = long long; const int N = 5e6; bool is_prime[N+5]; int d[N+5]; //d[i]=iの最小の素因数 int main(){ for(int i = 0; i < N; i++) is_prime[i]=true; //エラトステネス for(int i = 2; i < N; i++){ if(is_prime[i]) d[i] = i; for(int j = i + i; j < N; j += i){ is_prime[j] = false; if(is_prime[i] && d[j]==0) d[j] = i; } } is_prime[1] = false; int t; cin >> t; for(int i = 0; i < t; i++){ ll a; ll p; cin >> a >> p; if(is_prime[p]){ if(a%p!=0) cout << 1 << endl; else cout << 0 << endl; } else cout << -1 << endl; } return 0; }