#include <bits/stdc++.h>

using namespace std;

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

#define int long long

bool sieve[1000005];
vector<int>primes,v;
int m,n,a,b,nrgood;
int ans[20],k;

void ciur()
{
    sieve[0] = sieve[1] = true;
    for (int i = 4; i <= 1000000; i += 2)
        sieve[i] = true;
    for (int i = 3; i * i <= 1000000; i += 2)
        if (!sieve[i])
            for (int j = i * i; j <= 1000000; j += 2 * i)
                sieve[j] = true;
    primes.push_back(2);
    for (int i = 3; i <= 1000000; i += 2)
        if (!sieve[i])
            primes.push_back(i);
}

int number(int x)
{
    return a / x;
}

void afis()
{
    int d = 1;
    for (int i = 1; i <= k; i++)
        d *= v[ans[i]];
    if (k % 2 == 1)
        nrgood += number(d);
    else
        nrgood -= number(d);
}

void bkt(int p)
{
    if (p == k + 1)
        afis();
    else
    {
        for (int i = ans[p - 1] + 1; i <= n - k + p; i++)
        {
            ans[p] = i;
            bkt(p + 1);
        }
    }
}

void generare_combinari()
{
    for (int i = 1; i <= n; i++)
    {
        k = i;
        bkt(1);
    }
}

signed main()
{
    ciur();
    in >> m;
    for (int i = 1; i <= m; i++)
    {
        in >> a >> b;
        v.clear();
        v.push_back(0);
        n = 0;
        nrgood = 0;
        for (int j = 0; primes[j] * primes[j] <= b; j++)
        {
            if (b % primes[j] == 0)
            {
                v.push_back(primes[j]);
                n++;
                while (b % primes[j] == 0)
                    b /= primes[j];
            }
        }
        if (b != 1)
            v.push_back(b),n++;
        generare_combinari();
        out << a - nrgood << '\n';
    }
    return 0;
}