#include <fstream>
#include <cmath>
using namespace std;

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

long long a, b, n, div[10000], nrdiv = 0, rez = 0;
bool isPrim[1000010];
int divPrim[100001], nDiv;

void ciur() {
    int i, j;
    for(i = 2; i <= 1000000; ++i) {
        if(!isPrim[i]) {
            divPrim[++nDiv] = i;
            for(j = 2 * i; j <= 1000000; j += i)
                isPrim[j] = 1;
        }
    }
}

void doPinex(int last, int anad, long long sum) {
    long long i;
    if(anad != 0)
        if(anad % 2 == 0)
            rez += (a / sum);
        else
            rez -= (a / sum);
    for(i = last; i <= nrdiv; ++i)
        doPinex(i + 1, anad + 1, sum * div[i]);
}

int main() {
    int i, j;
    fin >> n;
    ciur();
    for(i = 1; i <= n; ++i) {
        fin >> a >> b;
        nrdiv = 0;
        for(j = 1; divPrim[j] * divPrim[j] <= b; ++j)
            if(b % divPrim[j] == 0) {
                div[++nrdiv] = divPrim[j];
                while(b % divPrim[j] == 0)
                    b /= divPrim[j];
            }
        if(b != 1)
            div[++nrdiv] = b;
        rez = a;
        doPinex(1, 0, 1);
        fout << rez << "\n";
    }
    fout.close();
    return 0;
}