#include <stdio.h>
#include <math.h>
#define ll long long
#define MAX_P 1000000
using namespace std;
ll n,a,b,fact[30];
int np[80000],nrp;
bool ciur[MAX_P];
void prec(){
    int i,j;
    for(i=2;i<MAX_P;i++)
        if(!ciur[i]){
            for(j=2*i;j<MAX_P;j+=i)
                ciur[j]=1;
            np[++nrp]=i;
        }
}
void solve(){
    ll t=0,d=0,i,j,sol=a,nr=0,prod=1;
    while(b>1){
        d++;
        if(b%np[d]==0){
            fact[++t]=np[d];
            while(b%np[d]==0)
                b/=np[d];
        }
        if((np[d]+1)*(np[d]+1)>b && b>1){
            fact[++t]=b;
            b=1;
        }
    }
    for(i=1;i<(1<<t);i++){
        for(j=0;j<t;j++)
            if((1<<j)&i){
                prod=prod*fact[j+1];
                nr++;
            }
        if(nr%2)
            nr=-1;
        else
            nr=1;
        sol=sol+nr*a/prod;
    }
    printf("%lld\n",sol);
}
int main(){
    int i;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    prec();
    scanf("%lld",&n);
    for(i=1;i<=n;i++){
        scanf("%lld %lld",&a,&b);
        solve();
    }
    return 0;
}