#include <bits/stdc++.h>

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

const int dim = 1e6 + 5;
const int Nmax = 1e6;

bitset <dim> ciur;
vector <int> prime;
int n;

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

int main()
{
    Eratostene();
    fin >> n;
    for(int i = 1 ; i <= n ; ++i)
        {
            long long a , b , rasp;
            vector <int> factori;
            fin >> a >> b;
            int k = 0; rasp = a;
            while(b > 1)
                {
                    if(prime[k] == 0) break;
                    int e = 0;
                    while(b % prime[k] == 0) b /= prime[k] , ++e;
                    if(e) factori.push_back(prime[k]);
                    ++k;
                }
            int N = (1 << factori.size());
            for(int j = 1 ; j < N ; ++j)
                {
                    int biti = 0;
                    long long r = 1;
                    for(int p = 0 ; p < (int) factori.size() ; ++p)
                        if(j & (1 << p))
                            {
                                biti++;
                                r *= factori[p];
                            }
                    if(biti % 2 == 1)
                        rasp -= a / r;
                    else
                        rasp += a / r;
                }
            fout << rasp << '\n';
        }
}