#pragma GCC optimize("fast-math")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define dim 1000005
using namespace std;
bitset<dim>ciur;
vector<int>primes;
long long test_cases, a, b;


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

ifstream fin("pinex.in");
ofstream fout("pinex.out");
int32_t main(int argc, char * argv[])
{
    sieve();
    fin >> test_cases;
    while(test_cases--)
    {
        fin >> a >> b;
        vector<int>divi;
        int k = 0;
        while(k < primes.size() && primes[k] * primes[k] <= b)
        {
            if(b % primes[k] == 0)
            {
                divi.push_back(primes[k]);
                while(b % primes[k] == 0)
                {
                    b /= primes[k];
                }
            }
            k++;

        }
        if(b > 1)
        {
            divi.push_back(b);
        }
        int nrdiv = divi.size();
        long long sol = 0, semn = 1, nrsub = 0, card = 0;  // la nr de sub par e minus la impar plus
        for(int i = 1; i < (1 << nrdiv); ++i)
        {
            nrsub = 0, card = 1, semn = 1;
            for(int j = 0; j < nrdiv; ++j)
            {
                if(i & (1 << j))
                {
                    nrsub++;
                    card *= 1ll *  divi[j];
                }
            }
            if(nrsub % 2)
            {
                semn = 1;
            }
            else
            {
                semn = -1;
            }
            sol += 1ll * semn * a / card;
        }
        fout << a - sol << '\n';

    }
    return 0;
}