#include <bits/stdc++.h>

using namespace std;

const int nmax=1000000;

vector <int> factori;
vector <int>  primi;
bool ch[nmax];

void ciur() {
    for(int i=2; i*i<=nmax; i++)
        if(ch[i]==false)
            for(int j=i*i; j<=nmax; j+=i)
                ch[j]=true;
    for(int i=2; i<=nmax; i++)
        if(ch[i]==false)
            primi.push_back(i);
}

void descomp(long long x) {
    for(int i=0; i<primi.size(); i++) {
        if(x%primi[i]==0) {
            factori.push_back(primi[i]);
            while(x%primi[i]==0)
                x/=primi[i];
        }
    }
    if(x>1)
        factori.push_back(x);
}
long long pinex(long long x) {
    long long s=0;
    long long n=(1<<factori.size())-1;
    for(long long i=1; i<=n; i++) {
        int p=1;
        int siz=0;
        for(int j=0; j<factori.size(); j++) {
            if((i&(1<<j))!=0) {
                p*=factori[j];
                siz++;
            }
        }
        if(siz%2==0)
            s-=x/p;
        else
            s+=x/p;
    }
    return s;
}

int main() {
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    short m;
    long long a, b;

    scanf("%hd", &m);
    ciur();
    while(m) {
        scanf("%lld%lld", &a, &b);
        descomp(b);
        printf("%lld\n", a-pinex(a));
        factori.clear();
        m--;
    }

    return 0;
}