#include <fstream>
#include <vector>
#include <iostream>
#define MAX 1000005
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int m;
long long a,b;
vector <int> v;
vector <int> pr;
bool ci[MAX];
void ciur()
{
    for(int i=2;i<MAX;++i)
    {
        if(ci[i]==0)
        {
            for(int j=i+i;j<MAX;j+=i)
            {
                ci[j]=1;
            }
            pr.push_back(i);
        }
    }
}
void div()
{
    for(int i=0;i<pr.size()&&i<b;++i)
    {
        if(b%pr[i]==0)
        {
            v.push_back(pr[i]);
        }
    }
    if(b>MAX)
        v.push_back(b);
}
int main()
{
    fin>>m;
    ciur();
    for(int i=0;i<m;++i)
    {
        v.clear();
        fin>>a>>b;
        div();
        int cop;
        long long s=0;
        int con=0;
        for(int j=0;j<(1<<v.size());++j)
        {
            int pr=1;
            cop=j+1;
            con=0;
            for(int k=0;k<v.size();++k)
            {
                if(cop & 1)
                {
                    pr*=v[k];
                    ++con;
                }
                cop=cop>>1;
            }
            if(pr!=1)
            {
                if(con%2==0)
                {
                    s=s-a/pr;
                }
                else
                {
                    s=s+a/pr;
                }
            }
        }
        fout<<a-s<<"\n";
    }
    return 0;
 }