#include <iostream>
#include <fstream>

using namespace std;
int prime[1000001];
int factor[1000001];
bool notPrime[1000001];

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

    int M, k = 0;
    fin >> M;

    notPrime[0] = notPrime[1] = true;
    for (int i = 2; i <= 1000000; ++i) {
        if (!notPrime[i]) {
            prime[k] = i;
            k += 1;
            for (int j = 2 * i; j <= 1000000; j += i) {
                 notPrime[j] = true;
            }
        }
    }

    for (int i = 0; i < M; ++i) {
        int A, B, cnt = 0, answer = 0;
        fin >> A >> B;
        for (int i = 0; i < k; ++i) {
            if (B % prime[i] == 0) {
                factor[cnt] = prime[i];
                cnt += 1;
                while (B % prime[i] == 0) {
                    B = B / prime[i];
                }
            }
            if (B > 1) {
                factor[cnt] = B;
            }
        }

        for (int mask = 1; mask < (1 << cnt); ++mask){
            int contor = 0;
            long long product = 1;
		    for (int i = 0; i < cnt; ++i){
			    if (mask & (1 << i)){
                    product *= factor[i];
                    contor += 1;
                }
		    }
            if (contor % 2) {
                answer += A/product;
            } else {
                answer -= A/product;
            }
	    }
	    fout << A - answer << " ";
    }
    return 0;
}