#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
vector <long long> v;
int p[1000100];
bool prime[1000100];
int dr = -1;
void ciur()
{
    int i, j;
    int n = 1000000;
    for(i = 4 ; i <= n ; i += 2)
        prime[i] = 1;
    for(i = 3 ; i * i <= n ; i += 2)
        if(prime[i] == 0)
            for(j = i * i ; j <= i ; j += i)
                prime[j] = 1;
    for(i = 2 ; i <= n ; i ++)
        if(prime[i] == 0)
            p[++dr] = i;
}

int main()
{
    ciur();
    int m, i, n, numere, j;
    long long nr, A, B, s;
    fin >> m;
    while(m--)
    {
        fin >> A >> B;
        v.clear();
        for(j = 0 ; 1ll * p[j] * p[j] <= B ; j++)
        {
            i = p[j];
            if(B % i == 0)
            {
                v.push_back(i);
                while(B % i == 0)
                    B /= i;
            }
        }
        if(B > 1)
        {
            v.push_back(B);
        }
        n = v.size();
        s = 0;
        for(i = 1 ; i < (1 << n) ; i++)
        {
            nr = 1;
            numere = 0;
            for(j = 0 ; (1<<j) <= i ; j++)
            {
                if(i & (1<<j))
                {
                    numere++;
                    nr = 1ll * nr * v[j];
                }
            }
            if(numere % 2 == 0)
            {
                s += 1ll * A / nr;
            }
            else
            {
                s -= 1ll * A / nr;
            }
        }
        fout << A + s << "\n";
    }
}