#include <bits/stdc++.h>
#define DIM 1000002

using namespace std;

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

int a,b,K;

int v[DIM],ciur[DIM],prim[DIM],primcnt;

int T;

int main(){

    fin >> T;

    for(int i=2;i<DIM;i++)
        if(!ciur[i]){
            for(int j=i+i;j<DIM;j+=i)
                ciur[j]=1;
            prim[++primcnt] = i;
        }

    while(T--){
        fin >> a >> b;
        K=0;

        for(int i=1;i<=primcnt && prim[i]<=b;i++)
            if(b%prim[i]==0)
                v[++K]=prim[i];

        int mask = (1<<K) - 1;
        int ans=0;

        for(int i=1;i<=mask;i++){
            int P=1,cnt=0;
            for(int j=0;j<K;j++)
                if((i&(1<<j))){
                    P*=v[j+1];
                    cnt++;
                }
            if(cnt%2)
                ans += a/P;
            else
                ans -= a/P;
        }

        ans = a - ans;

        fout << ans << "\n";
    }

    fin.close();fout.close();

    return 0;
}