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

using namespace std;

#define int long long

ifstream in("pinex.in");
ofstream out("pinex.out");
int q, a, b;
int prime[200005];
int k;
bool ciur[1000005];
vector<int> fact;

void build_ciur()
{
    ciur[0] = ciur[1] = 1;

    for(int i = 2; i<=1000000; i++)
    {
        if(ciur[i] == 0)
        {
            k++;
            prime[k] = i;

            for(int j = 2; i*j<1000000; j++)
            {
                ciur[i*j] = 1;
            }
        }
    }
}

signed main()
{
    build_ciur();

    in>>q;

    while(q--)
    {
        in>>a>>b;
        fact.clear();

        for(int i = 1; i<=k && prime[i] * prime[i] <= b; i++)
        {
            if(b % prime[i] == 0)
            {
                fact.push_back(prime[i]);
            }

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

        if(b > 1)
        {
            fact.push_back(b);
        }

        int ans = a;
        int stmax = (1 << fact.size());

        for(int mask = 1; mask < stmax; mask++)
        {
            int prod = 1;
            int cnt = 0;
            for(int i = 0; i<fact.size(); i++)
            {
                if((mask & (1 << i)))
                {
                    cnt++;
                    prod *= fact[i];
                }
            }

            int sum = a / prod;

            if(cnt % 2 == 1)
            {
                ans -= sum;
            }
            else
            {
                ans += sum;
            }
        }

        out<<ans<<'\n';
    }

    return 0;
}