#include <fstream>
#include <iostream>
#define MAX 1000005

using namespace std;

bool ciur[MAX + 1];
int prime[MAX];

void ciurInit()
{
    int i, j;

    for(i = 2; i * i <= MAX; i++)
        if(!ciur[i])
            for(j = i * i; j <= MAX; j += i)
                ciur[j] = 1;

    int k = 0;

    for(i = 2; i <= MAX; i++)
    {
        if(!ciur[i])
        {
            k++;
            prime[k] = i;
        }
    }
}

long long solve(int a, int b)
{
    long long i, cb, numarator, cpNumarator, numitor, raport, rest;

    cb = b;
    raport = a / b;
    rest = a % b;

    i = numarator = numitor = 1;

    while(prime[i] * prime[i] <= b)
    {
        if(b % prime[i] == 0)
        {
            numarator *= prime[i] - 1;
            numitor *= prime[i];

            while(b % prime[i] == 0)b /= prime[i];
        }

        i++;
    }

    if(b > 1)
    {
        numarator *= b - 1;
        numitor *= b;
    }

    cpNumarator = numarator;
    numarator = numarator * cb / numitor;
    //cout << numarator << " ";
    numarator *= raport;
    numarator += rest * cpNumarator / numitor;
    if(rest % numitor)numarator++;

    return numarator;
}

int main()
{
    long long m, i, a, b;

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

    ciurInit();

    fin >> m;

    for(i = 1; i <= m; i++)
    {
        fin >> a >> b;

        fout << solve(a, b) << '\n';
    }
}