#include <iostream>
#include <fstream>
#include <bitset>
#define CIUR 1000000

using namespace std;

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

bool f[105];
bitset <CIUR+1> ciur;
long long p, prim[CIUR+1];
long long n, a, cb, b, cnt, crt, par;
long long d[105], poz;

void clean(){
    for(int i=0; i<=100; i++)
        f[i]=0;
}

int main (){
    for(int i=2; i<=CIUR; i++)
        if(ciur[i] == 0){
            prim[++p]=i;
            if(1LL*i*i <= CIUR)
                for(int j=i*i; j<=CIUR; j+=i)
                    ciur[j]=1;
        }

    fin>>n;
    while(n--){
        fin>>a>>b;
        cnt=0;

        cb=b;
        d[0]=0;
        for(int i=1; prim[i]<=cb/prim[i] && cb != 1; i++)
            if(cb%prim[i] == 0){

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

                while(cb%prim[i] == 0)
                    cb/=prim[i];
            }
        if(cb != 1)
            d[++d[0]]=cb;


        clean();
        while(f[0] == 0){
            poz=d[0];
            while(f[poz] == 1){
                f[poz]=0;
                poz--;
            }
            f[poz]=1;

            if(poz == 0)
                break;


            par=0;
            crt=1;
            for(int i=1; i<=d[0]; i++)
                if(f[i] == 1){
                    crt*=d[i];
                    par=1-par;
                }

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