#include <bits/stdc++.h>
#define DIM 50001
#define int long long
#define MOD 666013

using namespace std;

ifstream fin("pinex.in");

ofstream fout("pinex.out");

int Q, a, b;

vector <int> get_divi(int n){

    vector <int> v;

    int d = 2;

    while(n > 1){

        if(n % d == 0){

            v.push_back(d);

            while(n % d == 0)

                n /= d;

        }

        if(d >= 3)

            d += 2;

        else d++;

        if(d * d > n && n > 1)

            d = n;

    }

    return v;

}

int solve(int a, int b){

    vector <int> v;

    v = get_divi(a);

    int ret = 0;

    for(int mask = 1 ; mask <= (1 << v.size()) - 1 ; mask++){

        int product = 1;

        for(int bit=0;bit<v.size();bit++)

            if((mask >> bit) & 1)

                product *= v[bit];

        if(__builtin_popcount(mask) % 2 == 1)

            ret += b / product;

        else ret -= b / product;

    }

    return ret;

}

int32_t main(){

    fin >> Q;

    while(Q--){

        fin >> a >> b;

        fout << a - solve(b, a) << "\n";

    }

}