#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>
#include <cmath>
#define P_MAX 1000000
using namespace std;
ifstream f ("pinex.in");
ofstream g ("pinex.out");
bitset < P_MAX + 1 > v;
vector < int > PN, Div;
long long a, b;
int m;

void PrimeClac()
{
    PN.clear();
    for (int i = 2; i < P_MAX; i++)
        if (!v[i])
        {
            for (int j = 2 * i; j <= P_MAX; j += i)
                v[j] = 1;
            PN.push_back(i);
        }
}
long long Sol()
{
    Div.clear();
    int d = 0;
    while (b > 1)
    {
        if (b % PN[d] == 0)
        {
            while (b % PN[d] == 0)
                b /= PN[d];
            Div.push_back(PN[d]);
        }
        if (PN[d] > sqrt(b) &&  b > 1)
        {
            Div.push_back(b);
            b = 1;
        }
        d++;
    }
    long long sol = a;
    for (int i = 1; i < (1 << Div.size()); i++)
    {
        long long prod = 1, nr = 0;
        for (int j = 0; j < Div.size(); j++)
            if (i & (1 << j))
                prod = 1LL * prod * Div[j],
                nr++;
        if (nr % 2) sol -= a / prod;
        else sol += a / prod;
    }
    g<<sol<<'\n';
}

int main()
{
    PrimeClac();
    f>>m;
    while (m--)
    {
        f>>a>>b;
        Sol();
    }
    return 0;
}