#include <iostream>
#include <fstream>
    
using namespace std;
using ll = long long;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

int n;
ll x,y;

ll gcd(ll a, ll b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

int main()
{
    fin >> n;
    while(n--){
        fin >> x >> y;
        int cnt = 0;
        for(int i = 1; i <= x; i++)
            if(gcd(i,y) == 1)
                cnt++;
        fout << cnt << '\n';
    }
    
    return 0;
}