#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <fstream>
#include <chrono>
using namespace std;
using namespace std::chrono;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<vvll> vvvll;
typedef vector<ull> vull;
typedef vector<vull> vvull;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vstring;
typedef vector<double> vdouble;

#define fs first
#define sc second
#define pb push_back
// forward strict for, most common
#define fors(i, a, n) for (int i = (int) (a); i < (int) (n); ++i)
// forward inclusive for
#define fori(i, a, n) for (int i = (int) (a); i <= (int) (n); ++i)
// backward for, inclusive
#define forb(i, n, a) for (int i = (int) (n); i >= (a); --i)

template <typename T>
void print(string name, vector<T>& v) {
    if (name.size()) cout << name << ": ";
    int s = (int) v.size();
    fors(i, 0, s) cout << v[i] << " ";
    cout << endl;
}
template<typename T> void print(vector<T>& v) { print("", v); }


class Problem {
public:
    vll primes;
    ll mb = 1000000000000;
//    ll mb = 100;
    ll mbs = sqrt(mb);

    vll isp = vll(mbs + 1, 1);
    ll a, b;
    vll d;
    vll arr;
    ll sum;

    void find_primes() {
        fori(i, 2, mbs)
        {
            if (isp[i] == 1) {
                primes.push_back(i);
                for (ll j = i; i * j <= mbs; j++)
                    isp[i * j] = 0;
            }
        }
    }

    vll find_prime_divisors(ll x) {
        vll xd;
        ll x2 = sqrt(x);
        ll x_ = x;
        for (ll p : primes) {
            if (p > x2) break;
            bool added = false;
            while (x_ % p == 0) {
                if (!added) xd.push_back(p), added = true;
                x_ /= p;
            }
        }

        bool x__prime = x_ > 1; // if x_ is prime
        ll x__2 = sqrt(x_);
        for (ll p : primes) {
            if (p > x__2) break;
            if (x_ % p == 0) {
                x__prime = false;
                break;
            }
        }

        if (x__prime) xd.push_back(x_);

        return xd;
    }

    void solve() {
        find_primes();
//        print("primes", primes);
        
        ifstream in("pinex.in");
        ofstream out("pinex.out");

        ll m;
        in >> m;

        fors(t, 0, m)
        {
            in >> a >> b;

            d = find_prime_divisors(b);
//            printf("Prime divisors of %d\n", b);
//            print(d);
            arr = vll(d.size() + 1);
            sum = 0;

            for (int l = 1; l <= (int) d.size(); l++) {
                ll sum_l = 0;
                back_track(0, l, sum_l);
//                cout << "sum_ " << l << " = " << sum_l << endl;
                if (l % 2) sum += sum_l;
                else sum -= sum_l;
            }

            ll res = a - sum;
            out << res << endl;
        }
    }

    void back_track(int k, int ds, ll& sum) {
        if (k == ds) {
            ll r = a;
            fors(i, 0, k)
                r /= d[arr[i]];
            sum += r;
//            printf("backtrack : sum += %d\n", r);
        }
        else {
            int sj = 0;
            if (k > 0) sj = arr[k - 1] + 1;
            int ej = d.size() - 1;
            for (int j = sj; j <= ej; j++) {
                arr[k] = j;
                back_track(k + 1, ds, sum);
            }
        }

    }
};

int main() {
    Problem p;
    p.solve();

    return 0;
}