#include <iostream>
#include <fstream>
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
bool pr[1000001];

int prim[78500], nrp = 1;
long long fact[31];
int nrf;
void ciur(int n)
{
    pr[0] = 1;
    pr[1] = 1;
    for(int i = 4; i <= n; i += 2)
        pr[i] = 1;
    for(int i = 3; i * i <= n; i += 2)
        if(pr[i] == 0)
            for(int j = i * i; j <= n; j += i)
                pr[j] = 1;
    prim[1] = 2;
    for(int i = 3; i <= n; i += 2)
        if(pr[i] == 0)prim[++nrp] = i;
}

void descf(long long B)
{
    nrf = 0;
    for(int i = 1; i <= nrp && 1LL * prim[i]*prim[i] <= B; i++)
        if(B % prim[i] == 0)
            {
                fact[++nrf] = prim[i];
                do
                    {
                        B /= prim[i];
                    }
                while(B % prim[i] == 0);
            }
    if(B > 1)
        fact[++nrf] = B;
}
int main()
{
    int m;
    long long A, B;
    ciur(1000000);
    f >> m;
    for(int i = 1; i <= m; i++)
        {
            f >> A >> B;
            descf(B);
            int nt = 1 << nrf;
            long long int card = A;
            for(int j = 1; j < nt; j++)
                {
                    long long int prod = 1;
                    int p2, nrdiv = 0;
                    for(int k = 0; (p2 = 1 << k) <= j; k++)
                        if((p2 & j) != 0)
                            {
                                prod *= fact[k + 1];
                                nrdiv++;
                            }
                    long long int t = A / prod;
                    if(nrdiv % 2 == 0)
                        card += t;
                    else
                        card -= t;
                }
            g << card << '\n';
        }
    return 0;
}