#include <fstream>
#define int long long
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int a, b, i, j, t, ans, v[10005], d, k;
signed main()
{
    fin>>t;
    while(t--)
    {
        fin>>a>>b;
        d=2;
        k=0;
        while(b>1)
        {
            if(b%d==0)
            {
                v[k++]=d;
                while(b%d==0)
                    b/=d;
            }
            d++;
            if(d*d>b)
                d=b;
        }
        ans=0;
        for(int mask=0; mask<(1<<k); mask++)
        {
            int pr=1, nr=0;
            for(int i=0; i<k; i++)
                if(mask&(1<<i))
                {
                    pr*=v[i];
                    nr++;
                }
            if(nr!=0)
            {
                if(nr%2==0)
                    ans-=a/pr;
                else
                    ans+=a/pr;
            }
        }
        fout<<a-ans<<'\n';

    }
    return 0;
}