#include <bits/stdc++.h>

using namespace std;
vector <long long> primes;
vector <long long> v;
const long long N = 1e6;
bitset <N> b;
void ciur()
{
    for(long long i = 2; i * i <= N; i++)
    {
        if(!b[i])
            for(long long j = i * i; j <= N; j+=i)
            {
                b[j] = true;
            }
    }
    for(long long i = 2; i <= N; i++)
        if(!b[i])
            primes.push_back(i);
}
int main()
{
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");
    ciur();
    long long m;
    cin >> m;
    while(m--)
    {
        long long a,b,c;
        cin >> a >> b;
        c = b;
        v.clear();
        for(auto x : primes)
        {
            if (1LL * x * x > b)
                continue;

            if(x <= b && b % x == 0)
                v.push_back(x);

            while (b % x == 0)
                b /= x;

        }
        if (b > 1)
            v.push_back(b);
        b = c;
        long long rez = 0;
        for(long long i = 1; i < (1 << v.size()); i++)
        {
            long long nr_bits = 0, p = 1;
            for(long long j = 0; j < v.size(); j++)
            {
                if(i & (1 << j))
                {
                    nr_bits++;
                    p *= v[j];
                }
            }
            if(nr_bits % 2 == 0)
            {
                rez -= (a / p);
            }
            else
            {
                rez += (a / p);
            }
        }
        cout << a - rez << "\n";
    }
    return 0;
}