#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
#define ll long long
const ll VALMAX=1+1e6;
const ll MAXPRIM=1e5+1;
int vprim[MAXPRIM];
bool ciur[VALMAX];
int vfact[101];
int main()
{
    int q,k,poz,n,cnt;
    ll a,b,rez;
    ll i,j,prod;
    fin>>q;
    k=0;
    for(i=2;i<=VALMAX;i++)
        if(!ciur[i]){
            for(j=2*i;j<=VALMAX;j+=i)
                ciur[j]=1;
            k++;
            vprim[k]=i;
        }
    while(q--)
    {
        fin>>a>>b;
        poz=0;
        n=0;
        while(b>1)
        {
            poz++;
            if(b%vprim[poz]==0)
            {
                n++;
                vfact[n]=vprim[poz];
                while(b%vprim[poz]==0)
                    b/=vprim[poz];
            }
            if(vprim[poz]*vprim[poz]>b && b>1)///b e nr prim
            {
                n++;
                vfact[n]=b;
                b=1;
            }
        }
        rez=a;
        for(i=1;i<(1<<n);i++)
        {
            prod=1;
            cnt=0;
            for(j=0;j<n;j++)
            {
                if(((i>>j)&1))
                {
                    prod=prod*vfact[j+1];
                    cnt++;
                }
            }
            if(cnt%2==1)
                rez-=a/prod;
            else
                rez+=a/prod;
        }
        fout<<rez<<'\n';
    }
    return 0;
}