#include <fstream>
#include <bitset>
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
long long i, j, n, m, d, k, divi, rez, biti, prod, cnt, a, b;
long long sol[100], v[100002];
bitset <1000002> f;
int main() {
    cin>>n;
   for(i=2;i<=1000000;i++){
    if(f[i]==0){
        v[++cnt]=i;
        for(j=i+i;j<=1000000;j+=i)
            f[j]=1;
    }
   }
    while(n--){
        cin>>a>>b;
        d=1;
        k=0;
        divi=v[d];
        rez=0;
        while(b!=1){
            if(b%divi==0){
                sol[++k]=divi;
                while(b%divi==0)
                    b/=divi;
            }
            d++;
            divi=v[d];
            if(d>cnt || divi*divi>b)
                divi=b;
        }
        for(i=1;i<(1<<k);i++){
            biti=0;
            prod=1;
            for(j=0;(1<<j)<=i;j++){
                if((i>>j)&1){
                    prod=prod*sol[j+1];
                    biti++;
                }
            }
            if(biti%2)
                rez+=a/prod;
            else
                rez-=a/prod;

        }
        cout<<a-rez<<"\n";
    }

}