#include <bits/stdc++.h>

using namespace std;

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

const int  BOUND = 1e6;

bitset <BOUND + 7> vis;

vector <int> prim;

void precalc()
{
    prim.push_back(2);

    for(int i = 3; i < BOUND; i += 2)
        if(vis[i] == false)
        {
            prim.push_back(i);

            if(1LL * i * i < BOUND)
                for(int j = i * i; j < BOUND; j += 2 * i)
                    vis[j] = true;
        }
}

long long solve(long long a, long long b)
{
    vector <int> divs;

    for(int i : prim)
        if(b % i == 0)
            divs.push_back(i);

    int n = divs.size();

    if(n == 0)
    {
        n++;
        divs.push_back(b);
    }

    long long sol = a;

    for(int i = 1; i < (1 << n); i++)
    {
        int mul = 1;

        long long p = 1;

        for(int j = 0; j < n; j++)
            if(i & (1 << j))
            {
                mul *= -1;
                p = p * divs[j];
            }

        sol += mul * a / p;
    }

    return sol;
}

main()
{
    precalc();

    int t;
    in >> t;

    while(t--)
    {
        long long a, b;
        in >> a >> b;

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