#include <bits/stdc++.h>

#define N_MAX 10000

using namespace std;

ifstream fin("pinex.in");

ofstream fout("pinex.out");

bool ciur[N_MAX + 5];

vector<int> divizori;
vector<int> primi;
int m;

void rez(long long int a)
{long long int rez1 = a;
    for (int i = 1; i < (1 << divizori.size()); i++)
    {
        long long int sclav = 1;
        int cnt = 0;
        for (int j = 0; j < divizori.size(); j++)
        {
            if ((1 << j) & i)
            {
                sclav *= divizori[j];
                cnt++;
            }
        }
        
        if (cnt % 2)
            rez1 -= a / sclav;
        else
            rez1 += a / sclav;
    }
    fout << rez1 << "\n";
}
int main()
{
    int nr;
    for (int i = 2; i <= N_MAX; i++)
    {
        if (!ciur[i])
        {
            primi.push_back(i);
            for (int j = i * i; j <= N_MAX; j += i)
            {
                ciur[j] = true;
            }
        }
    }
    fin >> m;
    for (; m--;)
    {
        long long int a, b;
        fin >> a >> b;
        long long int sclav = b;
        for (int i = 0; primi[i] * primi[i] <= b && sclav != 1; i++)
        {
            if (sclav % primi[i] == 0)
            {
                divizori.push_back(primi[i]);
            }
            while (sclav % primi[i]==0)
            {
                sclav /= primi[i];
            }
        }

        if (sclav != 1)
            divizori.push_back(sclav);
        rez(a);
        divizori.clear();
    }
}