#include <iostream>
#include <fstream>
#include <vector>
#define MAX 1000000

using namespace std;

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

int t;
bool viz[MAX+10];
vector <long long> prime, fact;

void sieve()
{   viz[0] = viz[1] = 1;
    for(int i=2; i<=MAX; i++)
        if(!viz[i])
            {   prime.push_back(i);
                for(int j=i+i; j<=MAX; j+=i) viz[j] = 1;
            }
}

int main()
{
    sieve();
    f >> t;
    while(t--)
        {   long long a, b, sol=0;
            fact.clear();
            f >> a >> b;
            for(int i=0; i<prime.size(); i++)
                {   if(prime[i] * prime[i] > b) break;
                    if(b % prime[i] == 0)
                        {   fact.push_back(prime[i]);
                            while(b % prime[i] == 0) b /= prime[i];
                        }
                }
            if(b != 1) fact.push_back(b);
            int n = fact.size();
            for(int i=1; i<(1<<n); i++)
                {   int nrb = 0, sign = 1;
                    long long prod = 1;
                    for(int j=0; j<n; j++)
                        if((i & (1 << j)) != 0) prod = prod * fact[j], nrb++;
                    if(nrb % 2 == 0) sign = -1;
                    sol = sol + sign * (a / prod);
                }
            g << a - sol << '\n';
        }
    return 0;
}