# 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 n;
    f >> n;

    for (int i = 1; i <= n; i++) {
        int s = 0;

        int a, b;
        f >> a >> b;

        for (int j = 1; j <= a; j++) {
            if (cmmdc (j, b) == 1) {
                s++;
            }
        }
        g << s << '\n';
    }

    return 0;
}