#include <fstream>
#include <bitset>

using namespace std;

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

int m, nrp, nr, x;
long long int a, b, prod;
bitset<1000101> c;
int p[100000], f[20], pr[20];

int main(){
    for(int i = 2; i <= 1000100; i++) {
        if(!c[i]) {
            for(int j = i + i; j <= 1000100; j += i) {
                c[j] = true;
            }
        }
    }
    for(int i = 2; i <= 1000100; i++) {
        if(!c[i]) {
            p[++nrp] = i;
        }
    }
    fin >> m;
    for(; m; m--) {
        fin >> a >> b;
        long long int aux = b, x = 0;
        for(int i = 1; i <= nrp && 1LL * p[i] * p[i] <= b; i++) {
            if(b % p[i] == 0) {
                pr[++x] = p[i];
                while(aux % p[i] == 0) {
                    aux /= p[i];
                }
            }
        }
        if(aux != 1) {
            pr[++x] = aux;
        }
        long long int r = 0;
        for(int i = 0; i <= x; i++) {
            f[i] = 0;
        }
        f[x] = 1;
        int j = 0;
        while(f[0] == 0) {
            nr = 0;
            prod = 1;
            for(int i = 1; i <= x; i++) {
                if(f[i] == 1) {
                    prod *= pr[i];
                    nr++;
                }
            }
            if(nr % 2 == 1) {
                r += a / prod;
            } else{
                r -= a / prod;
            }
            j = x;
            while(f[j] == 1) {
                f[j] = 0;
                j--;
            }
            f[j] = 1;
        }
        fout << a - r << "\n";
    }
    return 0;
}