#include <iostream>
#include <fstream>

using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int i,j,a,b,n,nr;
int cmmdc(int a,int b)
{
    if(b==0)
        return a;
    else
        return cmmdc(b,a%b);
}
int main()
{
    f>>n;
    while(n!=0)
    {
        nr=0;
        f>>a>>b;
        for(i=2;i<=a;i++)
            if(cmmdc(i,b)!=1)
                nr++;
        g<<a-nr<<'\n';
        n--;
    }
}