#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const string filename = "pinex";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

const int maxN = 1000000;
long long a, b, ans, val, nract;
int fact_primi[35];
bool marcat[maxN + 5];
vector <int> prime;

void ciur()
{
    marcat[0] = 1;
    marcat[1] = 1;
    for(int i = 2; i <= maxN; i++)
    {
        if(!marcat[i])
        {
            prime.push_back(i);
            for(int j = 2 * i; j <= maxN; j += i)
                marcat[j] = 1;
        }
    }
}

void solve()
{
    fin >> a >> b;
    int nr = 0;
    for(int x : prime)
    {
        if(x > b)
            break;
        if(b % x != 0)
            continue;
        fact_primi[++nr] = x;
        while(b % x == 0)
            b /= x;
    }
    ans = 0;
    if(b > 1)
        fact_primi[++nr] = b;
    for(long long c = 1; c < (1 << nr); c++)
    {
        val = 1, nract = 0;
        for(int i = 0; i < nr; i++)
            if(c & (1 << i))
            {
                nract++;
                val = 1LL * val * fact_primi[i + 1];
            }
        if(nract % 2 == 1)
            ans = ans + a / val;
        else
            ans = ans - a / val;
    }
    ans = a - ans;
    fout << ans << '\n';
}


int main()
{
    ciur();
    int nr_teste;
    fin >> nr_teste;
    while(nr_teste--)
        solve();
    return 0;
}