#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
vector <int> v;
int n,a,b;
int sub(int n){
    int l=1<<n,s=0;
    for (int i=1;i<=l;i++){
        int p=1,nr=0;
        for (int j=0;j<n;j++){
            if (i & (1<<j)) p=p*v[j],nr++;
        }
        //cout<<p<<' ';
        if (nr%2==0) s+=a/p;
            else s-=a/p;
    }
    //cout<<'\n';
    return s;
}
int main()
{
    int m;
    fin>>m;
    for (;m;m--){
        fin>>a>>b;
        int c=b,d=2;
        while (d*d<=c){
            int e=0;
            while (c%d==0) {
                c/=d;
                e++;
            }
            if (e) v.push_back(d);
            d++;
        }
        if (c!=1) v.push_back(c);
        //cout<<v.size()<<' ';
        fout<<sub(v.size())<<'\n';
        v.clear();
    }

    return 0;
}