#include <stdio.h>
#include <math.h>
#include <vector>

#define dim 1000001 //square root of maxB is the maximum prime divider of B

using namespace std;

int n;
long long a,b,rez;
bool noprnr[dim];
vector <int> prnr;
vector <long long> fprim;
vector <long long> stack;

void get_prnr()
{
    int index,i,j;
    noprnr[0]=true;
    noprnr[1]=true;
    prnr.push_back(2);
    for (i=3;i<dim-1;i+=2)
    {
        if(noprnr[i]==false)
        {
            prnr.push_back(i);
            for (j=2;j<dim;j++)
            {
                index = j*i;
                if (index<dim)
                    noprnr[index]=true;
                else
                    break;
            }
        }
        noprnr[i+1]=true;
    }
}

void get_fprim()
{
    int i;
    fprim.clear();
    int sqr = sqrt(b);
    for (i=0;(b>1)&(prnr[i]<=sqr);i++)//check all prime numbers smaller than the square root of b
    {
        if (b%prnr[i]==0)//if it's a prime factor
        {
            fprim.push_back(prnr[i]);//save it
            while (b%prnr[i]==0) //extract the prime factor from the number
                b/=prnr[i];
        }
    }
    if (b>1) //if b is still greater than 1 it's his own prime factor
        fprim.push_back(b);//save it
}

void fill(int level,int index)
{
    int i;
    if (level<fprim.size())
    {
        for (i=index;i<fprim.size();i++)
        {
            if (level == 0)
                stack.push_back(fprim[i]);
            else
                stack.push_back(stack[level-1]*fprim[i]);
            if (level%2==0)
                rez += a/stack[level];
            else
                rez -= a/stack[level];
            fill(level+1,i+1);
            stack.pop_back();
        }
    }
}

int main()
{
    int i;
    freopen("pinex.in","r",stdin);
    freopen("pinex.out","w",stdout);
    get_prnr();
    scanf("%d",&n);
    for (i=0;i<n;i++)
    {
        scanf("%lld %lld",&a,&b);
        get_fprim();
        rez=0;
        fill(0,0);
        rez=a-rez;
        printf("%lld\n",rez);
    }
    return 0;
}