#include <bits/stdc++.h>
#define END 1000000
using namespace std;

typedef unsigned long long ullong;

vector<size_t> numere_prime;

void Eratostene()
{
    bitset<END + 1> numere;

    for(size_t i = 2; i * i <= END; ++i)
    {
        if(numere[i] == 0)
        {
            for(size_t j = i * i; j <= END; j += i) numere[j] = 1;
        }
    }

    for(size_t i = 2; i <= END; i++)
    {
        if(numere[i] == 0)
        {
            numere_prime.push_back(i);
        }
    }
}

vector<size_t> divizoriPrimi(ullong B)
{

    vector<size_t> answer;
    size_t p = 0;
    size_t divizor = numere_prime[p];

    while(B - 1)
    {
        if(!(B % divizor)){
            answer.push_back(divizor);
            while(!(B % divizor)) B /= divizor;
        }

        divizor = numere_prime[++p];

        if(1LL * divizor * divizor > B) divizor = B;
    }

    return answer;
}

ullong pinex(ullong A, ullong B)
{
    vector<size_t> D = divizoriPrimi(B);
    ullong answer = A;


    for(ullong i = 1; i < ullong(1 << D.size()); ++i)
    {
        size_t contor = 0;
        unsigned long long produs = 1;

        for(size_t j = 0; j < D.size(); ++j)
        {
            if(i & ullong(1 << j))
            {
                contor++;
                produs = 1LL * produs * D.at(j);
            }
        }

        if(contor % 2 == 0) answer += A/produs;
        else answer -= A/produs;
    }

    return answer;
}


int main()
{
    ios_base::sync_with_stdio(false);

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

    Eratostene();

    size_t M;
    ullong A, B;

    fin >> M;

    for(size_t i = 1; i <= M; ++i)
    {
        fin >> A >> B;
        fout << pinex(A, B) << "\n";
    }
}