#include using namespace std; #include namespace mp=boost::multiprecision; int main(){ int N; cin>>N; long long A,P; vector M(5000001,1); M[1]=0; for(int i=2;i<5000001;i++){ if(M[i]){ for(int j=i*2;j<5000001;j+=i){ M[j]=0; } } } for(int i=0;i>A>>P; cout<<(M[P]*(1+(A%P!=0))-1)<