#include <bits/stdc++.h>

using namespace std;

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

int div(int a, vector<int> &v)
{
    int d=2;
    while(d*d <= a)
    {
        bool ok=false;
        while(a%d == 0)
        {
            ok=true;
            a/=d;
        }
        if(ok)
        {
            v.push_back(d);
        }
        d+=2;
        if(d == 4)
            d--;
    }
    if(a > 1)
        v.push_back(a);
}

int a, b;
vector<int> v;
int cnt=0;

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

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