#include <bits/stdc++.h>

using namespace std ;

ifstream fin("pinex.in");
ofstream fout("pinex.out");
#define cin fin
#define cout fout

#define N 1000004
bitset <N> c;
long long n, a, b, rez, nr, prod, prim[N], fact[30];

void ciur()
{
    c[1] = 1;
    for(long long i = 2 ; i <= N ; i++)
    {
        if(c[i] == 0)
        {
            prim[++prim[0]] = i;
            for(long long j = i*i ; j <= N ; j += i)c[j] = 1;
        }
    }
}
void divizori(long long x)
{
    fact[0] = 0;
    for(long long i = 1 ; i <= prim[0]  &&  prim[i]*prim[i] <= x ; i++)
    {
        if(x%prim[i] == 0)
        {
            fact[++fact[0]] = prim[i];
            while(x%prim[i] == 0)
            {
                x /= prim[i];
            }
        }
    }
    if(x > 1)fact[++fact[0]] = x;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin >> n;
    ciur();
    for( ; n ; n--)
    {
        cin >> a >> b;
        rez = 0;
        divizori(b);
        for(long long i = 1 ; i < (1<<fact[0]) ; i++)
        {
            nr = 0, prod = 1;
            for(long long j = 0 ; (1<<j) <= i ; j++)
            {
                if((1<<j)&i)
                {
                    nr++;
                    prod *= fact[j+1];
                }
            }
            if(nr%2 == 1)
            {
                nr = 1;
            }
            else nr = -1;
            rez += nr*a/prod;
        }
        cout << a-rez << '\n';
    }
    return 0;
}