#include <bits/stdc++.h>

using namespace std;

ifstream in ("pinex.in");
ofstream out ("pinex.out");

int n,a,b,v[1000000],traian;

int main()
{
    in>>n;
    for(int ii=1; ii<=n; ii++)
    {
        in>>a>>b;
        traian=0;
        int d = 2,p,cc=0;
        while(b > 1)
        {
            p = 0;
            while(b % d == 0)
            {
                ++p;
                b /= d;
            }
            if(p>0)
            {
                v[cc]=d;
                cc++;
            }
            ++ d;
            if(b>1 && d * d > b)
                d = b;
        }
        for(int i=0; i < (1<<cc); i++)
        {
            int p=1,traian2=0;
            for(int j=0; j < cc; j++)
            {
                if ((i & (1 << j)) > 0)
                {
                    p*=v[j];
                    traian2++;
                }
            }
            if(p==1)
                continue;
            if(traian2%2==0)
                traian-=floor(a/p);
            else
                traian+=floor(a/p);
        }
        out<<a-traian<<'\n';
    }
    return 0;
}