#include <bits/stdc++.h>

using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long a,b;
vector<long long> divizors;
int t;
signed main()
{
    fin>>t;
    while (t--)
    {
        fin>>a>>b;
        divizors.clear();
        long long rez=0;
        int d=2;
        while (d*d<=b)
        {
            int e=0;
            while (b%d==0) e++,b/=d;
            if (e>0) divizors.push_back(d);
            d++;
        }
        if (b>1) divizors.push_back(b);
        int lung=divizors.size();
        int m=(1<<lung);
        for (int i=1; i<m; i++)
        {
            int par=0;
            long long cnt=1;
            for (int j=0; j<lung; j++)
            {
                if (i&(1<<j))
                {
                    par++;
                    cnt=cnt*divizors[j];
                }
            }
            cnt=a/cnt;
            if (par%2==0) cnt=-cnt;
            rez=rez+cnt;
        }
        fout<<a-rez<<'\n';
    }
    return 0;
}