#include <bits/stdc++.h>

#define N_MAX 1000000

using namespace std;

ifstream fin("pinex.in");

ofstream fout("pinex.out");

bool ciur[N_MAX];

vector<int> divizori;
vector<int> primi;
int m;
void calcul()
{
    int i;
    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] = 1;
            }
        }
    }
}
void rez(int a, int nr)
{
    for (int i = 1; i < (1 << nr); i++)
    {
        int sclav = 1;
        int cnt = 0;
        for (int j = 0; j < nr; j++)
        {
            if ((1 << j) && i)
            {
                sclav *= divizori[j];
                cnt++;
            }
        }
        if (cnt % 2)
            a -= sclav;
        else
            a += sclav;
    }
    fout<<a<<"\n";
}
int main()
{
    int nr;
    calcul();
    fin >> m;
    for (; m--;)
    {
        nr = 0;
        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(i);
                nr++;
            }
            while (sclav % primi[i])
            {
                sclav /= primi[i];
            }
        }
        if (sclav != 1)
            divizori.push_back(sclav);
        rez(a, nr);
        divizori.clear();
    }
}