#include<fstream>
#include<bitset>
using namespace std;
int m, a, b, i, j, r, nrp, nr, prod, x, aux;
bitset<1000001> c;
int p[100000], f[20], pr[20];
ifstream fin("pinex.in");
ofstream fout("pinex.out");
int main(){
    for(i = 2; i <= 1000000; i++){
        if(c[i] == 0){
            for(j = i + i; j <= 1000000; j+= i){
                c[j] = 1;
            }
        }
    }
    for(i = 2; i <= 1000000; i++){
        if(c[i] == 0){
            p[++nrp] = i;
        }
    }
    fin>> m;
    for(; m; m--){
        fin>> a >> b;
        aux = b;
        x = 0;
        for(i = 1; i <= nrp && 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;
        }
        r = 0;
        for(i = 0; i <= x; i++){
            f[i] = 0;
        }
        f[x] = 1;
        while(f[0] == 0){
            nr = 0;
            prod = 1;
            for(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;
}