#include <bits/stdc++.h> 
using namespace std;
long long i,n,a,b,ciur[100500],j,CIUR,D[300],d,rs; bool e[1000005]; int main() { ifstream cin("pinex.in"); ofstream cout("pinex.out"); for (i=2; i<=1000000; i++) if (!e[i]) for (j=2; j<=1000000/i; j++) e[i*j]=true; for (i=2; i<=1000000; i++) if (!e[i]) ciur[++CIUR]=i; cin>>n; for (i=1; i<=n; i++) { cin>>a>>b; d=rs=0; for (j=1; ciur[j]<=sqrt(b); j++) { if (b%ciur[j]==0) { D[d++]=ciur[j]; while (b%ciur[j]==0) b/=ciur[j]; } } if(b>1) D[d++] = b; for (long long j=1; j<(1<<d); j++) { long long k=0,pr=1,semn=-1; for (long long z=0; z<d; z++) if ((1<<z)&j) pr*=D[z],k++; if (k%2) semn=1; rs+=(a/pr)*(semn); } cout<<a-rs<<'\n'; } }