#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

int v[100001], k;

void fact_primi(int n){
    int d=2; k=0;
    while(n>1){
        if(n%d==0){
            v[++k]=d;
            while(n%d==0){
                n/=d;
            }
        }
        d++;
        if(d*d>n){
            d=n;
        }
    }
}

int main()
{
    int n, i, j, l, nr=0;
    long long a, b, p=1, rez=0;
    f>> n;
    for(l=1; l<=n; l++){
        f>> a >> b; rez=a;
        fact_primi(b);
        for(i=0; i<pow(2, k); i++){
            nr=0; p=1;
            for(j=1; j<=k; j++){
                if((i>>(j-1))%2==1){
                    nr++; p*=v[j];
                }
            }
            if(nr==0){
                continue;
            }
            if(nr%2==0){
                rez+=a/p;
            } else {
                rez-=a/p;
            }
        }
        g<< rez << endl;
    }

    return 0;
}