#include <bits/stdc++.h>
using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

long long A, B, M;

int cmmdc(int a, int b) {
    if(b == 0)return a;
    else return cmmdc(b, a % b);
}

int main()
{
    f >> M;
    for(int i = 1; i <= M; i++) {
        f >> A >> B;
        int count = 0;
        for(int j = 1; j <= A; j++) {
            if(cmmdc(j, B) == 1)
                count ++;
        }

        g << count << '\n';
    }

    return 0;
}