#include <iostream>
#include <stdio.h>
using namespace std;
int n,nr_fprimi;
long long a,b;
int primii[79000];
long long factori[15];
bool ciur[1000000];
int factoriii()
{
    int p = 0 ;
    for(int i = 2 ; i  < 1000000 ; i++)
    {
        if(ciur[i] == false)
        {
            for(int j = i + i ; j  < 1000000 ; j += i)
                ciur[j] = true;
            primii[p] = i;
            p++;
        }
    }
    return p ;
}

int descompunere(long long b)
{
    int nr_fac = 0;
    for(int i = 0 ; i < nr_fprimi  && b != 1; i++)
        if( b % primii[i] == 0)
        {
            while(b % primii[i] == 0)
                b /= primii[i];
            factori[nr_fac++]= primii[i];
        }
    if( b != 1)
        factori[nr_fac++] = b;
    return nr_fac;
}

int sume(int nr)
{
    long long suma = 0;
    for(int x = 1 ; x < ( 1 << nr) ; x++)
    {
        int nr1 = 0;
        int p = 1;
        for(int j = 0 ; j < nr ; j ++)
            if((x & (1 << j)) != 0 )
            {
                p *= factori[j];
                nr1++;
            }
        if (nr1 % 2 == 0)
            suma -=a / p;
        else
            suma += a / p;
    }
    return suma;
}
int main()
{
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    scanf("%d",&n);
     nr_fprimi = factoriii();
    for(int i = 0 ; i < n ; i ++)
    {
        scanf("%lld %lld",&a,&b);
        int nr_fac = descompunere(b);
        long long rezultat = sume(nr_fac);
        printf("%lld\n",a - rezultat);
    }
    return 0;
}