#include using namespace std; using ll = long long; int main() { int t; cin >> t; vector prime(5*1000000+1,1); for(int i = 2;i<5*1000000+1;i++) { if(prime[i]) { for(int j = i*2;j<5*1000000+1;j+=i) { prime[j] = false; } } } prime[0] = prime[1] = false; while(t--) { int a,p; cin >> a >> p; if(prime[p]) { if(a%p==0) { cout<<0<