#include <iostream>
#include <fstream>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int cmmdc(int a, int b)
{
    if(b == 0)return a;
    return cmmdc(b, a % b);
}
int main()
{ int a,b,m;
    f >> m;
    for(int i = 1; i <= m; i++)
    {
        f >> a >> b;
        int nr = 0;
        for(int j = 1; j <= a; j++)
            if(cmmdc(j, b) == 1)nr++;
         g << nr << endl;
    }
    return 0;
}