#include <bits/stdc++.h>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
long long a,b,cnt;
int m;

int main()
{
    fin>>m;
    for(int i=0;i<m;i+=1){
        fin>>a>>b;
        for(long long j=1;j<=a;j+=1){
            if(__gcd(j,b)==1)
                cnt+=1;
        }
        fout<<cnt<<'\n';
        cnt=0;
    }
    return 0;
}