#include <bits/stdc++.h>

using namespace std;

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

long long t, a, b, m, k, q, rez;
long long p[1000005], diiv[100], x[100];

bitset <1000005> f;

void precalc (){
    long long i, j;
    for (i=1; ((i*i)<<1) + (i<<1)<=1000000; i++){
        if (f[i] == 0){
            for (j=((i*i)<<1) + (i<<1); (j<<1) + 1 <= 1000000; j+=(i<<1)+1){
                f[j] = 1;
            }
        }
    }
    p[1] = 2;
    m = 1;
    for (i=1; 2*i+1<=1000000; i++){
        if (f[i] == 0){
            p[++m] = 2*i+1;
        }
    }
}

void factorizare (long long n){
    long long d;
    k = 0;
    for (d=1; n!=1 && 1LL*p[d]*p[d]<=n; d++){
        if (n%p[d] == 0){
            diiv[++k] = p[d];
            while (n%p[d] == 0){
                n /= p[d];
            }
        }
    }
    if (n != 1){
        diiv[++k] = n;
    }
}

void calc (){
    long long p;
    p = 1;
    for (long long i=1; i<=k; i++){
        if (x[i] != 0){
            p *= diiv[i];
        }
    }
    if (q%2 == 0){
        p = -p;
    }
    if (p != -1 && p != 1){
        rez += (a/p);
    }
}

void bkt (long long n, long long k){
    if (k > n){
        calc();
    }
    else{
        x[k] = 0;
        bkt(n, k+1);
        x[k] = 1;
        q++;
        bkt(n, k+1);
        q--;
    }
}

void solve (long long a, long long b){
    factorizare(b);
    rez = 0;
    bkt (k, 1);
    fout << a - rez << "\n";
}

int main(){
    fin >> t;
    precalc();
    for (;t--;){
        fin >> a >> b;
        solve(a, b);
    }
    return 0;
}