#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];

int main()
{
    ka >> m;
    while(m--)
    {
        ka >> a >> b;
        int t = (int)sqrt(b);
        fact[0] = 0;
        if((b & 1) == 0)
            fact[++fact[0]] = 2;
        for(long long i = 3; i <= t; i += 2)
        {
            if(compus[i])
            {
                for(long long j = i * i; j <= t; j += i)
                    compus[j] = true;
                compus[i] = false;
            }
            else
            {
                if(b % i == 0)
                {
                    fact[++fact[0]] = i;
                    while(b % i == 0)
                        b /= 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';
    }
}