#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);
        for(int i = 3; i <= t; i += 2)
            for(int j = i * i; j <= t; j += i)
                compus[j] = true;
        fact[0] = 0;
        for(long long i = 2; i <= t; i++)
            if(!compus[i] && (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;
        }
        for(int i = 1; i <= t; i++)
            compus[i] = false;
        ki << sol << '\n';
    }
}