//Ilie Dumitru
#include<cstdio>

char prim[62501];
int N, nrprim[80000];

inline void setbit(int i){prim[i>>3]|=1<<(i&7);}
inline char getbit(int i){return prim[i>>3]&(1<<(i&7));}

void ciur()
{
    int i, j, n=1000000;
    nrprim[N++]=2;
    for(i=3;i<n;i+=2)
        if(!getbit(i>>1))
        {
            nrprim[N++]=i;
            for(j=i*i;j<n && j>0;j+=i)
                setbit(j>>1);
        }
}

void solve(long long int A, long long int B)
{
    int div[50], i, n=0;
    long long int j, max;
    for(i=0;i<N && B>=nrprim[i];i++)
    {
        if(!(B%nrprim[i]))
        {
            div[n++]=nrprim[i];
            while(!(B%nrprim[i]))
                B/=nrprim[i];
        }
    }
    if(B>1)
        div[n++]=B;
    long long int nr, p;
    long long int ans=A;
    for(j=1, max=((long long int)1)<<n;j<max;++j)
    {
        for(i=nr=0, p=1;i<n;++i)
        {
            if(j & (1<<i))
            {
                nr++;
                p*=div[i];
            }
        }
        nr=-((nr&1)<<1)+1;
        ans+=nr*(A/p);
    }
    printf("%lli\n", ans);
}

int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
    long long int B, A;
    int M;
    ciur();
    scanf("%i", &M);
    while(M--)
    {
        scanf("%lli%lli", &A, &B);
        solve(A, B);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}