#include <bits/stdc++.h>

using namespace std;

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

int m, prime_number[1000007], z, divizori[1000000];
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 k, int maxim, long long p)
{
    if (i == maxim)
    {
        if (maxim % 2 == 1)
        {
            rez = rez + a / p;
        }
        else
        {
            rez = rez - a / p;
        }
        return;
    }
    if (k > divizori[0]) return;
    Back(i + 1, k + 1, maxim, p * divizori[k]);
    Back(i, k + 1, maxim, p);
}

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, 1, i, 1);
        }
        fout << a - rez << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}