#include <iostream>
#include <fstream>
#define ull unsigned long long int
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");
ull gcd(ull a , ull b)
{
    ull r;
    while(b)
    {
        r = a%b;
        a = b;
        b = r;
    }
    return a;
}
ull solve1(ull a, ull b)
{
    ull nr = 0;
    for(ull i = 1 ; i <= a ; i ++)
        if(gcd(i,b) == 1)
            nr++;
    return nr;
}
int main()
{
    ull m,a,b;
    in >> m;
    while(m--)
    {
        in >> a >> b;
        out << solve1(a,b) << '\n';
    }
    return 0;
}