#include <bits/stdc++.h>
#define maxb (1<<20)
typedef long long ll;
using namespace std;
ll M,A,B,P[1<<17],p,C[maxb],D[100],d,num,k,rs;
int main() {
	ifstream cin("pinex.in");
	ofstream cout("pinex.out");
    for(int i = 2;i<maxb;i++) if(!C[i]){
        P[++p] = i;
        for(int j = i+i;j<maxb;j+=i) C[j] = 1;
    }
    cin >> M;
    while(M--){
        cin >> A >> B;
        rs = d = 0;
        for(int i = 1;P[i]<=sqrt(B);i++) if(B%P[i]==0){
            D[d++] = P[i];
            while(B%P[i] == 0) B/=P[i];
        } 
        if(B>1) D[d++] = B;
    
        for(int b=1;b<(1<<d);b++){
            k = 0;num=1;
            for(int i = 0;i<d;i++) if((1<<i)&b){num*=D[i];k++;}
            rs+=(A/num)*(k%2 ? 1 : -1);
        }
        cout << A-rs << '\n';
    }
}