#include <fstream>
#include <iostream>
#define MAX 1000001
#define NR_PRIME 78500

using namespace std;

bool Ciur[MAX], divC[MAX];
long long prime[NR_PRIME], divP[MAX];

void ciur()
{
    int i, j, l;

    for(i = 2; i * i < MAX; i++)
        if(!Ciur[i])
            for(j = i * i; j < MAX; j += i)
                Ciur[j] = 1;

    l = 0;
    for(i = 2; i < MAX; i++)
        if(!Ciur[i])
        {
            prime[l] = i;
            l++;
        }

    prime[l] = MAX;
    l++;
}

int descompunere(long long x)
{
    int i, j;

    i = j = 0;

    while(prime[i] * prime[i] <= x)
    {
        if(x % prime[i] == 0)
        {
            divP[j] = prime[i];
            j++;

            while(x % prime[i] == 0)
            {
                x /= prime[i];
            }
        }

        i++;
    }

    if(x > 1)
    {
        divP[j] = x;
        j++;
    }

    return j;
}

void bkt(long long a, long long n, long long k, long long &sol)
{
    if(k == n)
    {
        long long i, nr = 1;
        bool sign = 0;

        for(i = 0; i < n; i++)
        {
            //cout << divC[i];
            if(divC[i])
            {
                if(sign)sign = 0;
                else sign = 1;
                nr *= divP[i];
            }
        }

        if(sign)sol += a / nr;
        else if(nr > 1) sol -= a / nr;

        //cout << " " << sign << " " <<  sol << '\n';

        return;
    }

    divC[k] = 0;
    bkt(a, n, k + 1, sol);
    divC[k] = 1;
    bkt(a, n, k + 1, sol);
}

long long solve(long long a, long long b)
{
    long long n = descompunere(b);

    long long sol = 0;

    bkt(a, n, 0, sol);

    return a - sol;
}

int main()
{
    long long n, i, a, b;

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

    fin >> n;

    ciur();

    for(i = 0; i < n; i++)
    {
        fin >> a >> b;

        fout << solve(a, b) << '\n';
    }

    fin.close();
    fout.close();

    return 0;
}