#include <iostream>
#include <fstream>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;

const char iname[] = "pinex.in";
const char oname[] = "pinex.out";
const int MAX_D = 13;

typedef long long i64;

vector <int> bits[1 << MAX_D];

i64 solve(i64 a, i64 b) {
    int d[MAX_D], d_cnt = 0;

    if (b % 2 == 0) {
        while (b % 2 == 0)  b /= 2;
        d[d_cnt ++] = 2;
    }
    for (int i = 3; i * i <= b; i += 2) {
        if (b % i == 0) {
            while (b % i == 0)  b /= i;
            assert(d_cnt < MAX_D);
            d[d_cnt ++] = i;
        }
    }

    if (b > 1) {
        assert(d_cnt < MAX_D);
        d[d_cnt ++] = b;
    }

    i64 ans = 0;
    for (int i = 1; i < 1 << d_cnt; ++ i) {
        i64 p = 1;
        for (int j = 0; j < (int) bits[i].size(); ++ j)
            p *= d[ bits[i][j] ];
        ans += ((bits[i].size() & 1) ? +1 : -1) * (a / p);
    }
    return a - ans;
}

int main(void) {
    ifstream in(iname);
    ofstream out(oname);
    int m, a, b;

    for (int i = 1; i < 1 << MAX_D; ++ i) {
        for (int j = 0; j < MAX_D; ++ j) if ((i >> j) & 1)
            bits[i].push_back(j);
    }

    assert(in >> m);
    assert(1 <= m && m <= 500);
    while (m --) {
        assert(in >> a >> b);
        assert(1 <= a && a <= 1000000000000000000LL);
        assert(1 <= b && b <= 1000000000000LL);
        out << solve(a, b) << "\n";
    }
    in.close();
    out.close();
	return 0;
}