#include <fstream>
#include <vector>

using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
const int nmax = 1e6 + 6;
bool p[nmax];
vector <int> prime;
void ciur()
{
    int i, j;
    for(i = 4; i <= (nmax - 5); i += 2)
        p[i] = false;
    for(i = 3; i * i <= (nmax - 5); i += 2)
        if(!p[i])
            for(j = i * i; j <= (nmax - 5); j += 2 * i)
                p[j] = 1;
    prime.push_back(2);
    for(i = 3; i <= (nmax - 5); i += 2)
        if(!p[i])
            prime.push_back(i);
}
int main()
{
    long long n, i, j, q;
    ciur();
    cin >> q;
    while(q--){
        long long a, b;
        cin >> a >> b;
        vector <long long> divprim;
        for(i = 0; i < prime.size(); i++){
            if(prime[i] > b)
                break;
            if(b % prime[i] == 0){
                divprim.push_back(prime[i]);
                while(b % prime[i] == 0)
                    b /= prime[i];
            }
        }
        if(b > 1)
            divprim.push_back(b);
        long long nsize = (1 << divprim.size()), ans = a;
        for(i = 1; i < nsize; i++){
            long long nrbiti = 0, anscurr = 1;
            for(j = 0; j < divprim.size(); j++)
                if(i & (1 << j))
                    anscurr *= divprim[j], nrbiti++;
            if((nrbiti & 1))
                ans -= a / anscurr;
            else
                ans += a / anscurr;
        }
        cout << ans << "\n";
        /*for(i = 0; i < divprim.size(); i++)
            cout << divprim[i] << " ";
        cout << "\n";*/
    }
    return 0;
}