#include <cstdio>
#include <bitset>
#include <string.h>

using namespace std;

long long int n, a, b;
bitset <10005000> ciur;
long long div[10005000];
int o = 0;

long long prim[10005000];
int k=1;

void ciu()
{
    for(int i=2; i<=10005000; i++)
        if(ciur[i] == 0)
        {
            prim[k++] = i;
            for(int j=i+i; j<=10005000; j+=i)
                ciur[j] = 1;
        }
}


void diviz()
{
    for(int d=0; prim[d]*prim[d] <= b; d++)
    {
        if(b%prim[d] == 0)
        {
            while(b%prim[d] == 0)
                b/=prim[d];
            div[o++] = prim[d];
        }
    }
    if(b != 1)
        div[o++] = b;
}


long long subsir()
{
    long long nr=(1<<o);
    long long s=0;
    for(int i=1; i<nr; i++)
    {
        long long p=1;
        long long nre=0;
        for(int j=0; j<o; j++)
            if(i&(1<<j) != 0)
            {
                p=p*div[j];
                nre++;
            }
        if(nre%2 == 0)
            s=s-a/p;
        else s=s+a/p;
    }
    return s;
}



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


    scanf("%lld", &n);
    ciu();
    for(int i=1; i<=n; i++)
    {
        scanf("%lld %lld", &a, &b);
        diviz();
        printf("%lld\n", subsir());
        memset(div, 0, 1000005);
        o=0;
    }
    return 0;
}