#include <iostream>
#include <fstream>
#define NMAX
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int A,B,sol,M;
inline long long cmmdc(int a, int b)
{
    if(!b) return a;
    return cmmdc(b,a%b);
}
int main()
{
    fin>>M;
    for(int i = 1; i <= M; i++)
    {
        fin>>A>>B;
        int sol=0;
        for(int j = 1; j <= A; j++)
            if(cmmdc(j,B)==1) sol++;
        fout<<sol;
    }
    return 0;
}