#include <iostream>
#include <fstream>
#define nrmax 1000001

using namespace std;

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

int cnt, c, a, b, i, nr, n, nr_elem, p;
int prim[100001];
int factori[101];
bool ciur[nrmax];

int main()
{
    for(i = 2; i <= nrmax; ++i)
    {
        if(ciur[i] == false)
        {
            prim[++cnt] = i;
            for(int j = i + i; j < nrmax; j += i)
            {
                ciur[j] = 1;
            }
        }
    }
    fin >> c;
    while(c--)
    {
        fin >> a >> b;
        nr = 0;
        i = 1;
        while(b > 1 and prim[i] * prim[i] <= b)
        {
            if(b % prim[i] == 0)
            {
                factori[++nr] = prim[i];
                while(b % prim[i] == 0)
                {

                    b /= prim[i];
                }
            }
            ++i;
        }
        if(b > 1)
        {
            factori[++n] = b;
        }
        n = a;
        for(i = 1; i < (1LL << n); ++i)
        {
            nr_elem = 0;
            p = 1;
            for(int j = 0; j < n; ++j)
            {
                if(i & (1LL << j))
                {
                    ++nr_elem;
                    p *= factori[j + 1];
                }
            }
            if(nr_elem % 2 == 1)n -= (a / p);
            else n += (a / p);
        }
        fout << n << '\n';
    }
    return 0;
}