#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
bool v[105];
bitset <1000001> ciur;
long long p, prim[1000001];
long long n, a, b, cnt, crt, par;
long long d[105], poz;

void ciuR()
{
    for(int i=2; i<=1000000; i++)
        if(ciur[i] == 0){
            prim[++p]=i;
            if(1ll*i*i <= 1000000)
                for(int j=i*i; j<=1000000; j+=i)
                    ciur[j]=1;
        }
}
int main (){
    ciuR();
    f>>n;
    while(n--){
        f>>a>>b;
        cnt=0;
        d[0]=0;
        for(int i=1; prim[i]<=b/prim[i] && b != 1; i++)
            if(b%prim[i] == 0){

                d[++d[0]]=prim[i];

                while(b%prim[i] == 0)
                    b/=prim[i];
            }
        if(b != 1)
            d[++d[0]]=b;
         for(int i=0; i<=100; i++)
            v[i]=0;
        while(v[0] == 0){
            poz=d[0];
            while(v[poz] == 1){
                v[poz]=0;
                poz--;
            }
            v[poz]=1;
            if(poz == 0)
                break;
            par=0;
            crt=1;
            for(int i=1; i<=d[0]; i++)
                if(v[i] == 1){
                    crt*=d[i];
                    par=1-par;
                }

            if(par == 1)
                cnt+=a/crt;
            else
                cnt-=a/crt;
        }
        if(cnt < 0)
            g<<a+cnt<<"\n";
        else
            g<<a-cnt<<"\n";
    }
    return 0;
}