#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

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

bool isprime[1000005];
vector <int> primes;

void ciur()
{
    primes.push_back(2);

    for(int i = 3; i <= 1000000; i++)
        if(isprime[i] == false)
    {
        primes.push_back(i);

        for(long long j = 1LL * i * i; j <= 1000000; j += i)
            isprime[j] = true;
    }
}

int main()
{
    int N;

    fin >> N;

    ciur();

    for(int i = 1; i <= N; i++)
    {
        long long A, B;

        fin >> A >> B;

        vector <int> divisors;

        for(int i = 0; i < primes.size() && 1LL * primes[i] * 1LL * primes[i] <= B; i++)
            if(B % primes[i] == 0)
        {
            divisors.push_back(primes[i]);

            while(B % primes[i] == 0)
                B /= primes[i];
        }

        if(B != 1)
            divisors.push_back(B);

        int x = divisors.size();

        long long ans = 0;

        for(int mask = 1; mask <= (1 << x) - 1; mask++)
        {
            long long val = 1, ct = 0;

            for(int j = 0; (1 << j) <= mask; j++)
                if(mask & (1 <<j))
                    val *= 1LL * divisors[j], ct++;

            if(ct % 2 == 1)
            ans += A / val;
            else
                ans -= A / val;
        }

        fout << A - ans << '\n';
    }
    return 0;
}