#include <bits/stdc++.h>
#define DimMax 170

using namespace std;

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

int m, i;
long long a, b, total, sum;
long long v[DimMax];
int x[DimMax];
void Descompunere(long long p)
{
    long long d = 2;
    while(d * d <= p)
    {
        if(p % d == 0)
        {
        v[0]++;
        v[v[0]] = d;
        while(p % d == 0)
            p /= d;
        }
        d++;
    }
    if(p > 1)
    {
        v[0]++;
        v[v[0]] = p;
    }
}

void Adaugare()
{
    long long p = 1;
    for(int j = 1;j <= i;j++)
        p *= v[x[j]];
    sum += (a / p);
}

void Gen(int k)
{
    for(int j = x[k - 1] + 1;j <= v[0];j++)
    {
        x[k] = j;
        if(k == i)
            Adaugare();
        else
            Gen(k + 1);
    }
}

int main()
{
    fin>>m;
    for(int ii = 1;ii <= m;ii++)
    {
        fin>>a>>b;
        total = v[0] = 0;
        if(b == 1)
        {
            fout<<a<<'\n';
            continue;
        }
        Descompunere(b);
        for(int j = 1;j <= v[0];j++)
            total += (a / v[j]);
        for(i = 2;i <= v[0];i++)
        {
            sum = 0;
            Gen(1);
            if(i % 2 == 0) total -= sum;
            else total += sum;
        }
        fout<<a - total<<'\n';
    }
    return 0;
}