#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <fstream>
#include <algorithm>

#define ll long long
#define MAXP 1000000


using namespace std;
FILE *fin=fopen("pinex.in","r");
ofstream fout("pinex.out");
ll a,b,fact[30];
int fprim[80000];
bool prim[MAXP];
void preluc(){
    fill(prim+2,prim+MAXP,1);
    for(int i=2;i<MAXP;i++){
        if(prim[i]){
            for(int j=2*i;j<MAXP;j+=i){
                prim[j]=false;
            }
            fprim[++fprim[0]]=i;
        }
    }


}
void calc(int a,int b){
    ll t=0,d=0;
    while(b>1){
        d++;
        if(b%fprim[d]==0){
            fact[++t]=fprim[d];
            while(b%fprim[d]==0)
                b/=fprim[d];
        }
        if(fprim[d]>sqrt(b) and b>1){
            fact[++t]=b;
            b=1;
        }
    }
    ll sol=a;
    for(int i=1;i<(1<<t);i++){
        ll nr=0,prod=1;
        for(int j=0;j<t;j++){
            if ((1<<j)&i) {
                prod=1LL*prod*fact[j+1];
                nr++;
            }
        }
        if (nr%2) nr=-1;
        else nr=1;
        sol=sol+1LL*nr*a/prod;
    }
    fout<<sol<<'\n';
}
int main(){
    preluc();
    int m;
    fscanf(fin,"%d",&m);
    for(int i=1;i<=m;i++){
        int a,b;
        fscanf(fin,"%d%d",&a,&b);
        calc(a,b);
    }
    return 0;
}