#include <fstream>

using namespace std;

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

int m;
int p[78500], np;
bool notprim[1000005];
int pb[78500], npb;


void query(long long a, int b)
{
    npb = 0;

    for(int i = 1; (i <= np) && (p[i] * p[i] <= b); i++)
        if(b % p[i] == 0)
        {
            pb[npb++] = p[i];
            while(b % p[i] == 0)
                b /= p[i];
        }

    if(b != 1)
        pb[npb++] = b;

    long long suma = 0;


    for(int i = 1; i <= (1 << npb) - 1; i++)
    {
        int prod = 1;
        int paritate = 0;
        for(int j = 0; j < npb; j++)
            if(i & (1 << j))
            {
                paritate++;
                prod *= pb[j];
            }

        if(paritate % 2)
            suma += (long long)(a / prod);
        else
            suma -= (long long)(a / prod);
    }

    out << a - suma << '\n';
}

int main()
{
    in >> m;

    notprim[1] = 1;
    for(int j = 2; 2 * j <= 1000000; j++)
        notprim[2 * j] = 1;

    for(int i = 3; i <= 333333; i+= 2)
        for(int j = 3; i * j <= 1000000 ; j += 2)
            notprim[i * j] = 1;

    for(int i = 1; i <= 1000000; i++)
        if(notprim[i] == 0)
            p[++np] = i;

    for(int i = 1; i <= m; i++)
    {
        long long a;
        int b;
        in >> a >> b;
        query(a, b);
    }
    return 0;
}