#include <fstream>
//#include <iostream>
#include <math.h>

using namespace std;
ifstream ka("pinex.in");
ofstream ki("pinex.out");

const int N_MAX = 1000000;

int m;
long long a, b;
bool compus[N_MAX + 1];
long long fact[N_MAX + 1], primi[N_MAX + 1];

int main()
{
    ka >> m;
    primi[++primi[0]] = 2;
    for(long long i = 3; i <= N_MAX; i += 2)
    {
        if(compus[i])
        {
            for(long long j = i * i; j <= N_MAX; j += (2 * i))
                compus[j] = true;
        }
        else
            primi[++primi[0]] = i;
    }
    while(m--)
    {
        ka >> a >> b;
        int t = (int)sqrt(b);
        fact[0] = 0;
        for(int i = 1; i <= primi[0]; i++)
            if(b % primi[i] == 0)
            {
                fact[++fact[0]] = primi[i];
                while(b % primi[i] == 0)
                    b /= primi[i];
            }
        if(b > 1)
            fact[++fact[0]] = b;
        /*for(int i = 1; i <= fact[0]; i++)
            cout << fact[i] << " ";
        cout << '\n';*/
        int tt = fact[0];
        long long sol = a;
        for(int i = 1; i < (1 << tt); i++)
        {
            long long nr = 0, prod = 1;
            for(int j = 0; j < tt; j++)
                if(i & (1 << j))
                {
                    prod = 1LL * prod * fact[j + 1];
                    nr++;
                }
            if(nr % 2 == 1)
                nr = -1;
            else
                nr = 1;
            sol += 1LL * nr * a / prod;
        }
        ki << sol << '\n';
    }
}