#include <bits/stdc++.h>
#define NMAX 1000000

using namespace std;

int p[NMAX + 2],k,v[NMAX + 2];
bool f[NMAX + 2];

void ciur()
{
    for (int i = 4;i <= NMAX ;i += 2)
        f[i] = 1;
    for (int i = 3;i * i <= NMAX;i += 2)
        if (f[i] == 0)
            for (int j = i * i;j <= NMAX;j += 2 * i)
                f[j] = 1;
    p[++k] = 2;
    p[++k] = 3;
    int d = 5;
    while (d <= NMAX)
    {
        if (f[d] == 0)
            p[++k] = d;
        if (f[d + 2] == 0)
            p[++k] = d + 2;
        d += 6;
    }
}

int main()
{
    ifstream fin ("pinex.in");
    ofstream fout ("pinex.out");
    long long int n,a,b,p1,ans,i,k1;
    int nr;
    ciur();
    fin >> n;
    for (int t = 0;t < n;t++)
    {
        fin >> a >> b;
        i = 1;
        k1 = 0;
        while (p[i] * p[i] <= b && b > 1)
        {
            if (b % p[i] == 0)
            {
                v[++k1] = p[i];
                while (b % p[i] == 0)
                    b /= p[i];
            }
            i++;
        }
        if (b > 1)
            v[++k1] = b;
        ans = 0;
        for (int i = 1;i < (1 << k1);i++)
        {
            nr = 0;
            p1 = 1;
            for (int j = 0;j < k1;j++)
                if (i & (1 << j))
                {
                    p1 *= v[j + 1];
                    nr++;
                }
            if (nr % 2)
                ans += a / p1;
            else
                ans -= a / p1;
        }
        fout << a - ans << "\n";
    }
    return 0;
}