#include <iostream>
#include <stdio.h>
#include <cmath>

#define NMAX 1000003
#define ll long long

using namespace std;

ll n,a,b,i;
ll fact[30];

int prim[80003];
bool ciur[NMAX];

void eratostene(){
    int i,j;

    for(i=2;i<=NMAX;i++)
        if(!ciur[i]){
            for(j=i+i;j<=NMAX;j=j+i)
                ciur[j]=1;
            prim[++prim[0]]=i;

        }
}

void sol(){
    ll t=0,d=0,s=0,i,j,nr,prod;

    while(b>1){
        d++;

        if(b%prim[d]==0){
            fact[++t]=prim[d];

            while(b%prim[d]==0)
                b=b/prim[d];
        }

        if(prim[d]>sqrt(b) && b>1){
            fact[++t]=b;
            b=1;
        }
    }

    /*for(i=1;i<=t;i++)
        printf("%lli ",fact[i]);

    printf("\n");*/

    s=a;

    for(i=1;i<(1<<t);i++){

        nr=0,prod=1;

        for(j=0;j<t;j++)
            if((1<<j) & i){
                prod=1LL*prod*fact[j+1];
                nr++;
                }

        if(nr%2)
            nr=-1;
        else
            nr=1;

        s=s+1LL*nr*a/prod;


    }

    printf("%lli\n",s);


}

int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);

    scanf("%d",&n);

    eratostene();

    for(i=1;i<=n;i++){
        scanf("%lli%lli",&a,&b);
        sol();
    }


    return 0;
}