#include <fstream>
#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int t, a, b, i, d, ans;
signed main()
{
    fin>>t;
    while(t--)
    {
        fin>>a>>b;
        ans=0;
        d=2;
        vector <int> prim;
        while(b>1)
        {
            if(b%d==0)
            {
                prim.push_back(d);
                while(b%d==0)
                    b/=d;
            }
            d++;
            if(d*d>b)
                d=b;
        }
        int nr=prim.size();
        for(int mask=0; mask<(1<<nr); mask++)
        {
            int nr2=0, p=1;
            for(int j=0; j<nr; j++)
                if(mask&(1<<j))
            {
                nr2++;
                p*=prim[j];
            }
            if(nr2%2==1)
                ans+=a/p;
            else
                if(nr2)
                  ans-=a/p;
        }
        fout<<a-ans<<'\n';
    }
    return 0;
}