#include <bits/stdc++.h>

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

int v[10005];
int n0=0;

void div(int a)
{
    int d=2;
    n0=0;
    while(d*d <= a)
    {
        bool ok=false;
        while(a%d == 0)
        {
            ok=true;
            a/=d;
        }
        if(ok)
        {
            v[++n0]=d;
        }
        d+=2;
        if(d == 4)
            d--;
    }
    if(a > 1)
        v[++n0]=a;
}

int a, b;
int cnt=0;

void backontrack(int p, int prod, int m)
{
    if(p > n0)
        return;
    backontrack(p+1, prod, m);
    if(p > 0)
    {
        prod*=v[p];
        int add=a/prod;
        if(m%2 == 0)
            add*=-1;
        cnt+=add;
        backontrack(p+1, prod, m+1);
    }
}

int main()
{
    int n;
    fin>>n;
    for(int i=1; i<=n; i++)
    {
        fin>>a>>b;
        div(b);
        cnt=a;
        backontrack(0, 1, 0);
        fout<<cnt<<'\n';
    }
    return 0;
}