#include <fstream>
#include <math.h>

using namespace std;

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

const int N = 1000001;

int m, i, j, k, t, v[100010], n;
long long a, b, u, p, d[20], s, aux;
bool x[N];

void ciur(){
    for (i = 2; i < N; ++i) {
        if (x[i] == 0) {
            v[++k] = i;
            for(j = i + i; j<N; j += i) {
                x[j] = 1;
            }
        }
    }
}

int main(){
    ciur();
    fin >> m;
    for (i = 1; i <= m; ++i) {
        fin >> a >> b;
        u = b;
        s = 0;
        t = 0;
        j = 1;
        aux = sqrt(b * 1.0);
        while (u != 1 && v[j] <= aux){
            if (u % v[j] == 0) {
                d[++t] = v[j];
                while (u % v[j] == 0) {
                    u = u / v[j];
                }
            }
            j++;
        }
        if (u != 1) {
            d[++t] = u;
        }
        for (j = 0; j <= t; ++j) {
            x[j] = 0;
        }
        while(x[0] != 1) {
            j = t;
            while (x[j] == 1) {
                x[j] = 0;
                j--;
            }
            x[j] = 1;
            if (x[0] == 1) {
                break;
            }
            p = 1;
            n = 0;
            for (j = 1; j <= t; ++j) {
                if (x[j] == 1) {
                    n++;
                    p *= d[j];
                }
            }
            if (n % 2 == 0) {
                s -= a/p;
            } else {
                s += a / p;
            }
        }
        fout << a - s << "\n";
    }
    return 0;
}