#include <fstream>
#include <vector>
#include <iostream>
#define MAX 10000
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int m;
long long a,b;
vector <long long> v;
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;
            }
        }
    }
}
int main()
{
    fin>>m;
    ciur();
    for(int i=0;i<m;++i)
    {
        v.clear();
        fin>>a>>b;
        for(int k=2;k<=b;++k)
        {
            if(b%k==0 && ci[k]==0)
            {
                v.push_back(k);
            }
        }
        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;
 }