#include <fstream>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");
short m, div[13], cont;
int a, b, s, v, p;
int main()
{
    fin>>m;
    for(int i=1; i<=m; i++)
    {
        fin>>a>>b;
        cont=0;
        s=0;
        for(int d=2; d<=b; d++)
        {
            if(b%d==0)
            {
                cont++;
                div[cont]=d;
                while(b%d==0)
                    b/=d;
            }
        }
        int lim=1<<cont;
        for(int k=1; k<lim; k++)
        {
            v=0;
            p=1;
            for(int j=1; j<=cont; j++)
                if(k&(1<<(j-1)))
                {
                    v++;
                    p*=div[j];
                }
            if(v%2==1)
                s+=a/p;
            else
                s-=a/p;

        }
        fout<<a-s<<'\n';
    }
    return 0;
}