#include <bits/stdc++.h>
///M=500
///A=10^18
///B=10^12
using namespace std;
///
int m, a, b, i, j, k, x, sol, v;
bool ciur[1000000];
int primelist[1000000], primeone[1000000];
///
void buildCiur();
int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    scanf("%d", &m);
    buildCiur();
    while(m--){
        scanf("%d%d", &a, &b);
        sol=0;
        int total=0, div;
        for(int i=1; primelist[i]<=min(999999, b); ++i) if(!(b%primelist[i])) primeone[++total]=primelist[i];
        for(int i=1; i<(1<<total); ++i){
            int c=i; div=1; int pm=0;
            for(j=1; j<=total; ++j){
                if(c&1) {div*=primeone[j]; pm^=1;}
                c>>=1;
            }
            sol+=(a/div);
            if(!pm) sol-=2*(a/div);
        }
        printf("%d\n", a-sol);
    }
    return 0;
}
void buildCiur(){
    for(int i=2; i<1000000; ++i){
        if(ciur[i]) continue;
        primelist[++v]=i;
        for(int j=i+i; j<1000000; j+=i) ciur[j]=true;
    }
}