using namespace std;

#include<iostream>
#include<fstream>

ofstream fout("pinex.out");

int A,B,M,sum;
int cmmdc(int a,int b)
{int r;
    while(b)
    {
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
void cit()
{
    ifstream fin("pinex.in");
    fin>>M;
    for(int i=1;i<=M;i++)
    {fin>>A>>B;
    sum=0;
    for(int j=1;j<=A;j++)
        if(cmmdc(j,B)==1)
           sum++;
    fout<<sum<<"\n";
    }
    fin.close();
}

int main()
{
    cit();
    fout.close();
    return 0;
}