#include <fstream>
using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");
int div[300000];
int bdiv[300000];
int d[300000];
short int ex[1000004];
long long suma = 0,ct, a;

void bkt(int l)
{
    while(l)
    {
        if(d[l] < ct)
        {
            d[l]++;
            if(l < ct)
            {
                int sign = -1;
                if(l%2 == 1)
                    sign*=-1;
                long long prod = 1;
                for(int i = 1; i <= l; i++)
                {
                    prod *= bdiv[d[i]];
                }
                suma += sign*(a/prod);
                l++;
                d[l] = d[l-1];
            }
            else
            {
                int sign = -1;
                if(l%2 == 1)
                    sign*=-1;
                long long prod = 1;
                for(int i = 1; i <= l; i++)
                {
                    prod *= bdiv[d[i]];
                }
                suma += sign*(a/prod);
            }

        }
        else
            l--;
    }
}

int main()
{
    int m,b;
    fin>>m;
    div[1] = 2;
    int cnt = 1;
    for(long long i = 3; i <= 1000002; i += 2)
    {
        if(ex[i] == 0)
        {
            div[++cnt] = i;
            for(long long  j =i*i; j <= 1000002; j+=i)
                ex[j] = 1;
        }
    }
    for(int i = m; i != 0; i--)
    {
        suma = 0;
        fin>>a>>b;
        ct = 0;
        for(int i = 1; div[i] * div[i] <= b;i++)
        {
            if(b%div[i]==0){
                bdiv[++ct] = div[i];
                d[ct] = 0;
                b/=div[i];
            }
        }
        if(b)
            bdiv[++ct]= b;
        d[ct] = 0;
        bkt(1);
        fout<<a-suma<<"\n";
    }
    return 0;
}