#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;

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

const int MAXX = 1000000;

bitset < MAXX + 1 > ciur;

long long M, A, B, factori_primi[30], p;
int fprim[80000], poz;

void generare_ciur(int N)
{
    ciur[0] = ciur[1] = 1;
    for(int i = 4; i <= N; i += 2)
        ciur[i] = 1;
    for(int i = 3; i * i <= N; i += 2)
        if(ciur[i] == 0)
            for(int j = i * i; j <= N; j += i)
                ciur[j] = 1;
    fprim[++poz] = 2;
    for(int i = 3; i <= N; i += 2)
        if(ciur[i] == 0)
            fprim[++poz] = i;
}

long long solve(long long a, long long b)
{
    p=0;
    for(int i = 1; i <= poz && 1LL * fprim[i]*fprim[i] <= b; i++)
        if(b % fprim[i] == 0)
        {
            factori_primi[++p] = fprim[i];
            do
            {
                b /= fprim[i];
            }
            while(b % fprim[i] == 0);
        }
    if(b > 1)
        factori_primi[++p] = b;
    //
    long long ans = 0, k, product;
    int limit = 1 << p;
    for(int i = 1; i < limit; i++)
    {
        k = 0;
        product = 1;
        for(int j = 0; j < p; j++)
            if((1 << j)&i)
                product *= factori_primi[1 + j], k++;
        if(k % 2)
            ans += A / product;
        else
            ans -= A / product;
    }
    return A - ans;
}

int main()
{
    generare_ciur(MAXX);
    f >> M;
    while(M--)
    {
        f >> A >> B;
        g << solve(A, B) << '\n';
    }
    return 0;
}