#include <fstream>
#include<vector>
using namespace std;
ifstream in("pinex.in");
ofstream out("pinex.out");
#define int long long
int A;
int sum=0;
bool ciur[1000001];
int divizori[12];
int y=1;
int a[12];
vector<int> prim;
void rec(int x)
{
    if(x>1)
    {
        int prod=1;
        for(int i=1; i<x; i++)
        {
            prod=prod*divizori[a[i]];
        }
        if(x%2==0)
        {
            sum=sum-A/prod;
        }
        else
        {
            sum=sum+A/prod;
        }
    }
    for(int i=a[x-1]+1; i<=y-1; i++)
    {
        a[x]=i;
        rec(x+1);
    }
}
void gen(int r)
{
    for(int i=0; prim[i]*prim[i]<=r; i++)
    {
        if(r%prim[i]==0)
        {
            divizori[y]=prim[i];
            y++;
            while(r%prim[i]==0)
            {
                r=r/prim[i];
            }
        }
    }
    if(r>1){
    divizori[y]=r;
    y++;
    }
}
signed main()
{
    ciur[0]=ciur[1]=1;
    for(int i=2; i<=1000000; i++)
    {
        if(ciur[i]==0)
        {
            prim.push_back(i);
            for(int j=2; j*i<=1000000; j++)
            {
                ciur[i*j]=1;
            }
        }
    }
    int B,m;
    in>>m;
    for(int i=1; i<=m; i++)
    {
        in>>A>>B;
        y=1;
        gen(B);
        sum=A;
        rec(1);
        out<<sum<<endl;
    }

    return 0;
}