#include <iostream>
#include <fstream>
#define LL unsigned long long
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");

LL n;
int d[15], ds;

LL rec(LL s, int i, int mul){
    if(i==ds)
        return n/s*mul;
    return rec(s, i+1, mul)
    +rec(s*d[i], i+1, -mul);
}

int main(){
    int Q,x,i;
    fin>>Q;
    while(Q--){
        fin>>n>>x;
        n--; ds=0;
        for(i=2; x>1; i++){
            if(i*i>x)
                i=x;
            if(x%i==0){
                while(x%i==0)
                    x/=i;
                d[ds++]=i;
            }
        }
        fout<<rec(1,0,1)<<'\n';
    }
    return 0;
}