#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int MAXN = 1000000;

bool frecv[MAXN+3];
vector<int>prime;

void ciur()
{
    frecv[0] = frecv[1] = 1;
    for(int i = 2; i <= MAXN; i++)
        if(frecv[i] == 0)
            for(int j = i*2; j <= MAXN; j+=i)
                frecv[j] = 1;
    for(int i = 0; i <= MAXN; i++)
        if(frecv[i] == 0)
            prime.push_back(i);
}

long long putere(int b, int e)
{
    long long res = 1;
    for(int i = 0; i < e; i++)
        res *= b;
    return res;
}

void solve(long long a, long long b)
{
    vector<long long> factori;
    for(int i = 0; i < prime.size() && 1LL * prime[i] * prime[i] <= b; i++)
    {
        if(b % prime[i] == 0)
        {
            factori.push_back(prime[i]);
            while(b % prime[i] == 0)
                b /= prime[i];
        }
    }
    if(b != 1)
        factori.push_back(b);

    long long sum = a;
    long long lim = 1<<(factori.size());
    for(int i = 1; i <= lim; i++)
    {
        long long nr = 1;
        for(int j = 0; i>>j; j++)
        {
            if((i>>j) & 1)
                nr *= -factori[j];
        }
        sum += a / nr;
    }
    fout << sum << "\n";
}

int main()
{
    ciur();
    int m;
    fin >> m;
    for(int i = 0; i < m; i++)
    {
        long long a, b;
        fin >> a >> b;
        solve(a, b);
    }
    return 0;
}