#include <bits/stdc++.h>
#define BMAX2 1000003
using namespace std;
ifstream fin ("pinex.in");
ofstream fout ("pinex.out");

int m;
long long a, b;
long long nrd, d[BMAX2];

void divizori(int x)
{
    nrd = 0;
    if(x%2==0)
        d[++nrd]=2;
    while(x%2==0)
        x=x/2;
    for(int i = 3 ; i * i <= x ; i=i+2)
    {
        if(x % i == 0)
        {
            nrd++;
            d[nrd] = i;
        }
        while(x % i == 0)
        {
            x = x / i;
        }
    }
    if(x != 1)
    {
        nrd++;
        d[nrd] = x;
    }
}

long long pow2(int k)
{
    int p = 1;
    for(int i = 1 ; i <= k ; i++)
        p = p * 2;
    return p;
}

long long solve()
{
    long long p2 = pow2(nrd);
    long long p, nr1, r = 0;
    int semn = 1;

    for(long long i = 1 ; i <= p2 - 1 ; i++)
    {
        nr1 = 0;
        p = 1;
        semn = 1;
        for(int j = 1 ; j <= nrd ; j++)
        {
            if((i & (1<<(j - 1))) !=0)
            {
                nr1++;
                p = p * d[j];
            }
        }
        if(nr1 % 2 == 0)
            semn = -1;
        r = r + semn * (a/p);
    }
    return r;
}

int main()
{
    fin >> m;
    while(m > 0)
    {
        fin >> a >> b;
        divizori(b);
        fout << a - solve() << '\n';
        m--;
    }
    return 0;
}