#include <bits/stdc++.h>

using namespace std;

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

const int e6 = 1e6;

bool ciur[e6+5];
int primes[e6];
int crp[e6];

int main()
{
    int m,a,b;
    fin >> m;

    int crt = 0;
    for(int i=2 ; i<=e6 ; ++i)
    {
        if(!ciur[i])
        {
            primes[++crt]=i;

            for(int j=2*i ; j<=e6 ; j+=i)
            {
                ciur[j] = true;
            }
        }
    }

    while(m--)
    {
        fin >> a >> b;

        int cr = 0;
        for(int i=1 ; i<=crt ; ++i)
        {
            if(b%primes[i]==0)
            {
                crp[++cr]=primes[i];
            }
            while(!(b%primes[i]))
                b/=primes[i];
            if(b==1)
                break;
        }
        if(cr==0)
            crp[++cr]=b;

        int ans = 0;

        for(int i=1 ; i<(1<<(cr)) ; ++i)
        {
            int oc = 0;
            int nn = 1;
            for(int j=1 ; j<=cr ; ++j)
            {
                if((i>>(j-1))&1)
                {
                    oc++;
                    nn *= crp[j];
                }
            }

            if(oc%2)
                ans += a/nn;
            else
                ans -= a/nn;
        }
        fout << a-ans << '\n';
    }

    return 0;
}