#include <fstream>
#include <math.h>
using namespace std;
char V[10000002];
int P[100000];
long long pd, A, B, s;
int T, rb, i, j, x, X[100], nd, p;
int main(){
    ifstream f("pinex.in");
    ofstream g("pinex.out");
    for (i=2;i<=1000000;i++) {
        if (V[i] == 0){
            P[++p] = i;
            for (j=i+i;j<=1000000;j+=i)
                V[j] = 1;
        }
    }
    f>>T;
    for (;T;T--) {
        f>>A>>B;
        s = 0;
        x = 0;
        rb = (int)sqrt(B*1.0);
        for (i=1;P[i]<=rb && B!=1;i++) {
            if (B%P[i] == 0) {
                X[++x] = P[i];
                while (B%P[i] == 0) {
                    B/=P[i];
                }
            }
        }
        if (B!=1) {
            X[++x] = B;
        }
        for (i=1;i<(1<<x);i++) {
            pd = 1;
            nd = 0;
            for (j=0;j<x;j++)
                if ((i>>j)&1) {
                    pd *= X[j+1];
                    nd++;
                }
            if (nd%2 == 1)
                s += A/pd;
            else
                s -= A/pd;
            }
        g<<A-s<<"\n";
    }
}