#include <fstream>
#include <bitset>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int f[1000010];
bitset<110> l;
long long a,b,nr,i,j,k,w[50010],sub,n,p,q,v[300010],d,sol;
int main(){
    fin>>q;
    for(i=2;i<=1000000;i++)
        if(f[i]==0){
            v[++k]=i;
            for(j=2*i;j<=1000000;j+=i)
                f[j]=1;
        }
    for(;q--;){
        fin>>a>>b;
        nr=b;
        p=0;
        sol=0;
        d=1;
        while(nr!=1&&v[d]<=nr/v[d]){
            if(nr%v[d]==0){
                w[++p]=v[d];
                while(nr%v[d]==0){
                    nr/=v[d];
                }
            }
            d++;
        }
        if(nr!=1)
            w[++p]=nr;
        l.reset();
        while(l[0]==0){
            sub=0;
            j=p;
            n=1;
            while(l[j]==1){
                l[j]=0;
                j--;
            }
            l[j]=1;
            if(j==0)
                break;
            for(i=1;i<=p;i++)
                if(l[i]==1){
                    sub++;
                    n*=w[i];
                }
            if(sub%2==1)
                sol+=a/n;
            else
                sol-=a/n;
        }
         if(sol>0)
            fout<<a-sol<<"\n";
        else
            fout<<sol+a<<"\n";
    }

    return 0;
}