#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

long long A, B, k=0, d=2, mult[30];
void descompunere() {
    d=2;
    while(B>1) {
        if (B%d==0){
            mult[k++]=d;
            while (B%d==0) {
                B=B/d;
            }
        }

        if (B>1 && d*d>B) {
            mult[k++]=B;
            B=-1;
        }
        d++;
    }
    for (int i=0; i<k; ++i) {
        //cout << mult[i] << ' ' ;
    }
    //cout <<"A"<< '\n';
}
int main()
{   long long prod=1,ct=0,m;
    fin >> m;
    while (m!=0) {
        fin >> A >> B;
        k=0;
        descompunere();
        //cout << k << '\n';
        long long sol=0;
        for (int i=1; i<(1<<k) ; ++i) {
            prod=1;
            ct=0;
            for (int j=0; j<k; ++j) {
                if((i>>j)&1==1){
                    prod=prod*mult[j];
                    ct++;
                }
            }
            if(ct%2==0) {
                sol=sol-(A/prod);
            }
            else {
                sol=sol+(A/prod);
            }
            //cout << prod << ' ' << sol <<'\n';
        }
        fout << A-sol <<'\n';
        m--;
        //cout <<'\n';
    }
    return 0;
}