#include <bits/stdc++.h>

using namespace std;

ifstream inf("pinex.in");
ofstream outf("pinex.out");

int m, a, b, sol, nr;
vector<int> d, cd;
bitset<1000010> bst;

void bkt(int ,int ,int );

int main()
{
    inf>>m;
    bst[1]=1;
    d.push_back(2);
    for(int i=3; i<=1000010; i+=2)
    {
        if(!bst[i])
        {
            d.push_back(i);
            for(int j=3*i; j<=1000010; j+=(2*i))
                bst[j]=1;
        }
    }
    for(;m;m--)
    {
        inf>>a>>b;
        cd.resize(0);
        for(auto it:d)
        {
            if(b==1)
                break;
            if(b%it==0)
                cd.push_back(it);
            while(b%it==0)
                b/=it;
        }
        if(b>1)
            cd.push_back(b);
        sol=a;nr=1;
        bkt(1, cd.size(), 0);
        outf<<sol<<'\n';
    }
    return 0;
}

void bkt(int c,int m,int l)
{
    if(c>m)
        return;
    for(int i=l; i<m; i++)
    {
        nr*=cd[i];
        if(c&1)
            sol-=a/nr;
        else
            sol+=a/nr;
        bkt(c+1, m, i+1);
        nr/=cd[i];
    }
}