#include <bitset>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");
const long long kMax = 1e6 + 5;
long long A, B;
bitset<kMax> isPrime;
vector<long long> primeList, divB;

void sieve()
{
    isPrime.set();
    isPrime[0] = isPrime[1] = false;

    primeList.push_back(2);
    for (long long i = 4; i < kMax; i += 2)
        isPrime[i] = false;

    for (long long i = 3; i < kMax; i += 2)
    {
        if (isPrime[i])
        {
            primeList.push_back(i);
            for (long long j = i * i; j < kMax; j += i)
                isPrime[j] = false;
        }
    }
}


int main()
{
    sieve();
    int t = 0;
    fin >> t;
    while (t--)
    {
        fin >> A >> B;

        long long cb = B;
        for (size_t i = 0; i < primeList.size() && cb != 1; ++i)
        {
            if (!(cb % primeList[i]))
            {
                divB.push_back(primeList[i]);
                while (!(cb % primeList[i]))
                    cb /= primeList[i];
            }
        }
        if (cb != 1)
            divB.push_back(cb);

        long long notInSet = 0;
        int sz = divB.size(), pwr = (1 << sz);
        for (int bitMask = 1; bitMask < pwr; ++bitMask)
        {
            int bitsSet = 0;
            long long factor = 1;
            for (int i = 0; i < sz; ++i)
            {
                if (bitMask & (1 << i))
                {
                    ++bitsSet;
                    factor *= divB[i];
                }
            }

            if (bitsSet % 2)
                notInSet += (A / factor);
            else
                notInSet -= (A / factor);
        }

        fout << A - notInSet << '\n';

        divB.clear();
    }
    return 0;
}