#include <fstream>
using namespace std;

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

long long a, b, n, div[1000], nrdiv = 0, rez = 0;

void doPinex(int last, int anad, int sum) {
    int 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;
    for(i = 1; i <= n; ++i) {
        fin >> a >> b;
        nrdiv = 0;
        for(j = 2; j * j <= b; ++j) {
            if(b % j == 0) {
                div[++nrdiv] = j;
                while(b % j == 0)
                    b /= j;
            }
        }
        if(b != 1)
            div[++nrdiv] = b;
        rez = a;
        doPinex(1, 0, 1);
        fout << rez << "\n";
    }
    fout.close();
    return 0;
}