#include <fstream>
#include <cstring>
#include <bitset>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
 
bitset<1000001> B;
 
int w[100];
long long P[300000];
long long x[100];
 
long long a, b, e, nr, y, sol, k, i, j, p, m;
 
int main() {
    for (i=2;i<=1000000;i++)
        if (!B[i]) {
            P[++p] = i;
            for (j=i+i;j<=1000000;j+=i)
                B[j] = 1;
        }
    fin>>m;
    for (;m--;) {
        fin>>a>>b;
        e = b;
        k = 0;
        for (i=1;P[i]*P[i]<=b && e!=1;i++) {
            if (e%P[i] == 0) {
                x[++k] = P[i];
                while (e%P[i] == 0)
                    e/=P[i];
            }
        }
        if (e!=1) {
            x[++k] = e;
        }
 
        memset(w, 0, sizeof(w));
        sol = 0;
        while (!w[0]) {
            j = k;
            while (w[j] == 1) {
                w[j] = 0;
                j--;
            }
            w[j] = 1;
            if (j == 0)
                break;
            nr = 0;
            y = 1;
            for (j=1;j<=k;j++) {
                nr+=w[j];
                if (w[j])
                y *= x[j];
            }
            if (nr&1)
                sol += a/y;
            else
                sol -= a/y;
        }
        if (sol > 0)
            fout<<a-sol<<"\n";
        else
            fout<<a+sol<<"\n";
    }
 
    return 0;
}