#include <iostream>
#include <fstream>
#include <bitset>
#define MAX 1000003
#define sq 1000

using namespace std;

ifstream in("pinex.in");
ofstream out("pinex.out");

unsigned long long factF[50];
bitset<50> sol;
unsigned long long S;
unsigned long long D;
long long rez;
unsigned long long nr;
unsigned long long tD = 1;
bitset<MAX> ciur;
unsigned long long primes[100000];
int k=1;

void fact(unsigned long long n, unsigned long long M) {
    unsigned long long cnt = 1;
    for(int i = 1; primes[i] <= n && i < k; i++) {
        if(n%primes[i] == 0) {
            factF[cnt++] = primes[i];
            while(n%primes[i] == 0)
                n /= primes[i];
        }
    }
    if(n > 1)
        factF[cnt++] = n;
    cnt--;
    long long sol = 0;
    for(int i = 1; i < (1<<cnt); i++) {
        long long nr = 0;
        long long prod = 1;
        for(int j = 0; j < cnt; j++) {
            if((1<<j)&i) {
                prod *= 1LL*factF[j+1];
                nr++;
            }
        }
        if(nr%2 == 0)
            sol -= 1LL*M/prod;
        else
            sol += 1LL*M/prod;
    }

    out << M-sol << '\n';
}

int main() {

    unsigned long long n,a,b;
    in >> n;

    primes[k++] = 2;
    for(int i = 3; i < MAX; i += 2) {
        if(!ciur[i]) {
            primes[k++] = i;
            if(i > sq)
                continue;
            for(long long j = 1LL*i*i; j < MAX; j += i)
                ciur[j] = 1;
        }
    }

    for(unsigned long long i = 1; i <= n; i++) {

        in >> a >> b;
        fact(b, a);

    }

    return 0;
}