#include <bits/stdc++.h>

#define ll long long
#define sqrtB 1000005

using namespace std;

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

int M;
ll A, B;
bool c[sqrtB];
vector <int> primes;

vector <ll> getPrimeDiv(ll B)
{
    vector <ll> ret;
    for(auto it : primes)
        if(B % it == 0)
        {
            ret.push_back(it);
            while(B % it == 0)
                B /= it;
        }
    if(B != 1)
        ret.push_back(B);
    return ret;
}

ll solve(ll A, ll B)
{
    vector <ll> div;
    div = getPrimeDiv(B);
    ll ret = A;
    for(int i = 1; i < (1 << div.size()); i++)
    {
        int cnt = 0;
        ll prod = 1;
        for(int j = 0; (1 << j) <= i; j++)
            if(i & (1 << j))
                prod *= div[j], cnt++;
        if(cnt % 2 == 1)
            ret -= A / prod;
        else
            ret += A / prod;
    }
    return ret;
}

int main()
{
    for(int i = 2; i <= 1000000; i++)
        c[i] = true;
    c[1] = false;
    for(int i = 2; i <= 1000; i++)
        if(c[i])
            for(int j = i * i; j <= 1000000; j += i)
                c[j] = false;
    for(int i = 2; i <= 1000000; i++)
        if(c[i])
            primes.push_back(i);
    for(fin >> M; M; M--)
    {
        fin >> A >> B;
        fout << solve(A, B) << "\n";
    }
    return 0;
}