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

using namespace std;

bool ciur[1000001];

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

int d[1000001], nrd;

void addDiv(int dd, int &n)
{
    if(ciur[dd] == 0 && n % dd == 0)
    {
        nrd++, d[nrd] = dd;
        while(n % dd == 0)
            n /= dd;
    }
}

void getDivs(int n)
{
    nrd = 0;
    if(!(n & 1))
        nrd++, d[nrd] = 2, n >>= 1;
    for(int i = 3; i * i <= n; i += 2)
        addDiv(i, n), addDiv(n / i, n);
    if(n > 1e6 || ciur[n] == 0)
        nrd++, d[nrd] = n;
}

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, j;
    sieve();
    cin >> m;
    for(i = 1; i <= m; i++)
    {
        cin >> a >> b;
        getDivs(b);
        cout << pinex(a) << "\n";
    }
    return 0;
}