#include <bits/stdc++.h>

const std :: string FILENAME = "pinex";

std :: ifstream f (FILENAME + ".in");

std :: ofstream g (FILENAME + ".out");

const int NMAX = 1e6 + 1;

int q;

long long a;

long long b;

std :: vector <int> p;

std :: bitset <NMAX> c;

std :: vector <int> fact;

void precalc()
{
    c[0] = c[1] = true;

    for(int i = 2; i <= NMAX; i ++)
    {
        if(c[i] == false)
        {
            for(int j = 2; i * j <= NMAX; j ++)
            {
                c[i * j] = true;
            }
        }
    }

    for(int i = 2; i <= NMAX; i ++)
    {
        if(c[i] == false)
        {
            p.push_back(i);
        }
    }
}

inline long long solve()
{
    long long ans = a;

    for(int mask = 1; mask < (1 << fact.size()); mask ++)
    {
        int bit = 0;

        long long prod = 1;

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

                bit ++;
            }
        }

        int semn = (bit % 2 == 0) ? 1 : -1;

        ans += semn * (a / prod);
    }

    return ans;
}

int main()
{
    precalc();

    f >> q;

    while(q --)
    {
        f >> a >> b;

        long long aux = b;

        int i = 0;

        while(i < (int)p.size())
        {
            if(aux % p[i] == 0)
            {
                fact.push_back(p[i]);

                while(aux % p[i] == 0)
                {
                    aux /= p[i];
                }
            }

            i ++;

            if(p[i] > aux)
            {
                break;
            }
        }

        g << solve() << '\n';

        fact.clear();
    }

    return 0;
}