#include <iostream>
#include <fstream>

using namespace std;

ifstream f("pinex.in");
ofstream g("pinex.out");

long long v[100001], a, b, cnt, M;

void divizori()
{
    cnt = 0;
    for(int d = 2; d * d <= b; ++d)
        if(b % d == 0)
        {
            v[++cnt] = d;
            while(b % d == 0)
                b /= d;
        }
    if(b > 1)
        v[++cnt] = b;
}
void pinex()
{
    long long lim = (1 << cnt), k, mc, D = a;
    for(int i = 1; i < lim; ++i)
    {
        k = 0, mc = 1;
        for(long long j = 0; (1 << j) <= i; ++j)
            if(i & (1 << j))
            {
                k++;
                mc *= v[j + 1];
            }
        if(k % 2 == 0) D += a / mc;
        else D -= a / mc;
    }
    g << D << '\n';
}

int main()
{
    f >> M;
    while(M--)
    {
        f >> a >> b;
        divizori();
        pinex();
    }
    f.close();
    g.close();
    return 0;
}