#if 1
#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); }
#endif

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;
    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(m__, 0, m)
        {
            in >> a >> b;

            d = find_prime_divisors(b);
//            printf("Prime divisors of %d\n", b);
//            print(d);
            sum = 0;

            int t = (int) d.size();
            fors(i, 1, (1 << t)) {
                ll res_i = a;
                ll ci = 0;
                fors(j, 0, t) {
                    if ((1 << j) & i) res_i /= d[j], ci++;
                }
                if (ci % 2) sum += res_i;
                else sum -= res_i;
            }

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

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

    return 0;
}