#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    vector<bool> A(10000000,true);
    A[0]=false,A[1]=false;
    for(int i=2;i<=10000000/i;i++){
        if(!A[i])continue;
        for(int j=i*2;j<10000000;j+=i)A[j]=false;
    }
    int T;
    cin>>T;
    while(T--){
        int a,P;
        cin>>a>>P;
        if(!A[P])puts("-1");
        else if(a%P==0)puts("0");
        else puts("1");
    }
}