#include<stdio.h>
#include<bitset>
#include<algorithm>
#include<iostream>
#include<vector>
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define MOD 1000000007
using namespace std;
int N,np[1001000];
long long A,B;
vector<int> primes;

int main() {
	freopen("pinex.in","r",stdin);
	freopen("pinex.out","w",stdout);
	//freopen("input.in","r",stdin);
	for(int i=2;i<=1000000;++i) {
        if(!np[i]) {
            primes.pb(i);
            for(int j=2;i*j<=1000000;++j) {
                np[i*j] = 1;
            }
        }
    }
    scanf("%d",&N);
    for(int t=1;t<=N;++t) {
        long long rez = 0;
        scanf("%lld%lld",&A,&B);
        vector<long long> v;
        for(auto p: primes) {
            if(B%p == 0) {
                v.pb(p);
                while(B%p == 0) B /= p;
            }
        }
        if(B!=1) {
            v.pb(B);
        }
        int k = v.size();
        for(int b=0;b<(1<<k);++b) {
            int nr = 0;
            int x = b;
            long long z = 1;
            for(int i=0;i<k;++i) {
                if(x%2) {
                    ++nr;
                    z *= v[i];
                }
                x /= 2;
            }
            if(nr%2 == 0) {
                rez += A/z;
            } else {
                rez -= A/z;
            }
        }
        printf("%lld\n",rez);
    }
    return 0;
}