#include <fstream>
#include <vector>
#include <iostream>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int m;
long long a,b;
vector <int> v;
int main()
{
    fin>>m;
    for(int i=0;i<m;++i)
    {
        v.clear();
        fin>>a>>b;
        if(b%2==0)
        {
            v.push_back(2);
            while(b%2==0)
            {
                b/=2;
            }
        }
        int d=3;
        while(d*d<=b)
        {
            if(b%d==0)
            {
                v.push_back(d);
                while(b%d==0)
                {
                    b/=d;
                }
            }
            d+=2;
        }
        if(b!=1)
            v.push_back(b);
        int cop;
        long long s=0;
        int cf=-1,con=0,an=-5;
        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(con!=an)
            {
                cf*=-1;
            }
            an=con;
            if(pr!=1)
            {
                s+=cf*(a/pr);
            }
        }
        fout<<a-s<<"\n";
    }
    return 0;
 }