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

using namespace std;

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

int a,b,K;

int v[DIM];

int T;

int main(){

    fin >> T;

    while(T--){
        fin >> a >> b;
        int aux=b;
        K=0;
        for(int i=2;i<=aux;i++)
            if(aux%i==0){
                v[++K]=i;
                while(aux%i==0)
                    aux/=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;
}