#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <bitset>

#define INFL "pinex.in"
#define OUTFL "pinex.out"

using namespace std;

void read() {
}

#define nmax 1000001

int m, n;
long long A, B;

bitset<nmax> p;
vector<int> primes;

void solve() {
    p[0] = p[1] = 1;
    primes.push_back(2);
    for(int i=3; i<nmax; i+=2) {
        if(!p[i]) {
            primes.push_back(i);

            for(long long j = (1LL * i * i); j < nmax; j += (i<<1))
                p[j] = 1;
        }
    }

    n = primes.size();

    scanf("%d", &m);

    while(m--) {
        scanf("%lld%lld", &A, &B);

        vector<int> d;
        for(int i=0; i < n && primes[i] * primes[i] <= B; ++i) {
            int f = 0;

            while(B % primes[i] == 0) {
                B /= primes[i];
                f = 1;
            }

            if(f) {
                d.push_back(primes[i]);
            }
        }

        if(B > 1) {
            d.push_back(B);
        }

        int k = d.size();

        long long ans = A;

        for(int msk = 1; msk < (1<<k); ++msk) {
            long long prod = 1LL;
            int cnt = 0;

            for(int i=0; i<k; ++i) {
                if( msk & (1<<i) ) {
                    ++cnt;
                    prod *= d[i];
                }
            }

            ans += (cnt & 1 ? -1LL : 1LL) * A / prod;
        }

        printf("%lld\n", ans);
    }
}

int main() {
//#define ONLINE_JUDGE 1
#ifndef ONLINE_JUDGE
	freopen(INFL, "r", stdin);
	freopen(OUTFL, "w", stdout);
#endif

	read();
	solve();

	return 0;
}