#include <iostream>
#include <fstream>
#include <cmath>
#define int long long

using namespace std;

bool ciur[1000001];
int d[101], nrd, prime[80001], nrp;

void sieve()
{
    int i, j;
    ciur[0] = ciur[1] = 1;
    for(i = 2; i * i <= 1e6; i++)
        if(ciur[i] == 0)
        {
            prime[++nrp] = i;
            for(j = i * i; j <= 1e6; j += i)
                ciur[j] = 1;
        }
}

void getDivs(int n)
{
    int i = 0;
    nrd = 0;
//    while(n > 1)
//    {
//        i++;
//        if(n % prime[i] == 0)
//        {
//            d[++nrd] = prime[i];
//            while(n % prime[i] == 0)
//                n /= prime[i];
//        }
//        if(prime[i] > sqrt(n) && n > 1)
//            d[++nrd] = n, n = 1;
//    }
}

int pinex(int a)
{
    int i, j, cnt, p, semn, rez = a;
    for(i = 1; i < (1 << nrd); i++)
    {
        cnt = 0, p = 1, semn = 1;
        for(j = 0; j < nrd; j++)
            if((1 << j) & i)
                p = p * d[j + 1], cnt++;
        if(cnt & 1)
            semn = -1;
        rez += semn * a / p;
    }
    return rez;
}

signed main()
{
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");
    int m, a, b, i;
    sieve();
    cin >> m;
    for(i = 1; i <= m; i++)
    {
        cin >> a >> b;
        getDivs(b);
        cout << pinex(a) << "\n";
    }
    return 0;
}