#include <iostream>
#include <fstream>

using namespace std;

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

int n, nrd, f[100005];
long long a, b, sol, d[100005];

void dvd(long long &nr, long long x){
    int e=0;
    while(nr%x == 0){
        e++;
        nr/=x;
    }
    if(e != 0)
        d[++nrd]=x;
}

void bt(int k, int lst, int cnt, long long prd){

    if(k > 1){
        if(cnt%2 == 1)
            sol += a/prd;
        else
            sol -= a/prd;
    }

    if(k > nrd)
        return;

    for(int i=lst+1; i<=nrd; i++)
        bt(k+1, i, cnt+1, prd*d[i]);
}

int main (){
    fin>>n;
    while(n--){
        fin>>a>>b;
        sol=0;
        nrd=0;

        dvd(b, 2);

        for(long long i=3; i<=b/i; i+=2)
            dvd(b, i);
        if(b != 1)
            d[++nrd]=b;

        bt(1, 0, 0, 1);
        fout<<a-sol<<"\n";
    }
    return 0;
}