#include <bits/stdc++.h>

using namespace std;

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

int m, prime_number[78499], z, divizori[78499], stiva[78499];
bool isPrim[1000007];
long long a, b, sum, rez;

void Ciur()
{
    isPrim[0] = isPrim[1] = true;
    for (int i = 4; i <= 1000000; i += 2) isPrim[i] = true;
    for (int i = 3; i * i <= 1000000; i += 2)
    {
        if (isPrim[i] == false)
        {
            for (int j = i * i; j <= 1000000; j += 2 * i)
            {
                isPrim[j] = true;
            }
        }
    }
    prime_number[++z] = 2;
    for (int i = 3; i <= 1000000; i += 2)
    {
        if (isPrim[i] == false)
        {
            prime_number[++z] = i;
        }
    }
}

void Back(int i, int maxim, long long p, int k)
{
    if (i == maxim)
    {
        if (maxim % 2 == 1)
        {
            rez = rez + a / p;
        }
        else
        {
            rez = rez - a / p;
        }
        return;
    }
    for (int j = stiva[k - 1] + 1; j <= divizori[0]; ++j)
    {
        stiva[k] = j;
        Back(i + 1, maxim, p * divizori[j], k + 1);
    }
}

int main()
{
    Ciur();
    fin >> m;
    while (m--)
    {
        fin >> a >> b;
        divizori[0] = 0;
        for (int i = 1; prime_number[i] * prime_number[i] <= b; ++i)
        {
            if (b % prime_number[i] == 0)
            {
                divizori[++divizori[0]] = prime_number[i];
                while (b % prime_number[i] == 0) b = b / prime_number[i];
            }
        }
        if (b > 1) divizori[++divizori[0]] = b;
        rez = 0;
        for (int i = 1; i <= divizori[0]; ++i)
        {
            Back(0, i, 1, 1);
        }
        fout << a - rez << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}