#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

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

vector <int> prime;

void desc(long long n, vector <long long> &div)
{
    unsigned int i = 0;
    while (i < prime.size() && prime[i] * prime[i] <= n)
    {
        if (n % prime[i] == 0)
        {
            div.push_back(prime[i]);

            while (n % prime[i] == 0)
                n /= prime[i];
        }
        i++;
    }

    if (n != 1)
        div.push_back(n);
}

long long pinex(long long a, long long b)
{
    vector <long long> div;
    desc(b, div);
    
    unsigned int n = div.size();
    long long rez = 0;

    for (unsigned int i = 0; i < (1 << n); i++)
    {
        unsigned int nr = 0;
        long long p = 1;
        for (unsigned int j = 0; j < n; j++)
        {
            if (i & (1 << j))
            {
                nr++;
                p *= div[j];
            }
        }
        
        if (nr % 2 == 0)
            rez += a / p;
        else
            rez -= a / p;
    }

    return rez;
}

int main()
{
    int t;
    f >> t;

    bitset<1000001> ciur;

    for (int i = 2; i * i <= 1000001; i++)
        if (!ciur[i])
            for (int j = i * i; j <= 1000001; j+= i)
                ciur[j] = 1;

    for (int i = 2; i <= 1000001; i++)
        if (!ciur[i])
            prime.push_back(i);

    for (int k = 0; k < t; k++)
    {
        long long a, b;
        f >> a >> b;

        long long rez = pinex(a, b);

        g << rez << '\n';
    }

    f.close();
    g.close();
    return 0;
}