#include <bits/stdc++.h>
#define llt long long

using namespace std;

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

const llt MAX_CIUR = 1000000 + 5;
bitset<MAX_CIUR> c;
vector<llt> prime;
llt a,b;

void ciuruiala(){
    for(llt i = 2; i<MAX_CIUR; ++i)
        if(c[i] == 0){
            prime.push_back(i);
            for(llt j = 1; j*i<MAX_CIUR; ++j)
                c[i*j] = 1;
        }
}

bool prim(llt n){
    return binary_search(prime.begin(), prime.end(), n);
}

llt solve ( ){

    llt rez = 0;

    vector<llt> d;
    llt cb = b;
    for(auto i : prime){
        if(b % i == 0)
            d.push_back(i);
        while(cb%i == 0)
            cb/=i;
         if(cb == 1)
            break;
    }

    llt cd = d.size();

     for(llt i = 0; i < (1 << d.size()); i++)
        {
            llt k = 0, num = 1;

            for(llt j = 0; j < d.size(); j++)
            {
                if((1<<j) & i)
                {
                    num *= d[j];
                    k++;
                }
            }

            /// daca cardinalul multimii e par, includem, altfel excludem (wikipedia)

            if (k%2 == 0)
                rez += a/num;
            else rez -= a/num;
        }
        return rez;
}

int main()
{
    ciuruiala();

    llt t; fin >> t;

    while(t--){
        fin >> a >> b;
        fout<<solve()<<"\n";
    }

    return 0;
}