#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1e6 + 7;
const int LMAX = 107;

long long nr, p[NMAX], v[LMAX];
int ciur[NMAX];

void makeCiur()
{
    int aux;
    aux = 0;
    ciur[0] = 1;
    ciur[1] = 1;
    for (int i = 2; i <= 1000000; i++)
    {
        if (ciur[i] == 0)
        {
            p[++aux] = i;
            for (int j = 2 * i; j <= 1000000; j += i)
            {
                ciur[j] = 1;
            }
        }
    }
}

int main()
{
    makeCiur();

    int t;
    fin >> t;
    while (t--)
    {
        long long a, b;
        fin >> a >> b;

        long long x = b;
        int aux = 0;

        for (int i = 1; p[i] * p[i] <= b && x != 1; i++)
            if (x % p[i] == 0)
            {
                v[++aux] = p[i];
                while (x % p[i] == 0)
                {
                    x = x / p[i];
                }
            }


        if (x != 1)
            v[++aux] = x;


        int ans = 0;
        for (int i = 1; i < (1 << aux); i++)
        {
            nr = 0;
            x = 1;
            for (int j = 0; j < aux; j++)
                if ((1 << j) & i)
                {
                    x *= v[j + 1];
                    nr++;
                }


            nr % 2 == 1 ? ans -= a / x : ans += a / x;
        }

        fout << (ans > 0 ? a - ans : a + ans) << "\n";
    }
    return 0;
}