#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e6, P = 8e4;
short t;
long long prim[P], j, nr, a, b, prod, ans, nr = 0;
bitset<N> np;

int main(){
    for(int i = 2; i < N; i++){
        if(!np[i]){
            for(int j = 2 * i; j < N; j += i)
                np[j] = 1;
        }
    }

    for(int i = 2; i < N; i++){
        if(!np[i])
            prim[j++] = i;
    }

    f >> t;
    while(t--){
        f >> a >> b;
        ans = a;
        vector<long long> d;
        j = 0;
        while(prim[j] * prim[j] <= b){
            if(b % prim[j] == 0){
                d.push_back(prim[j]);
                b /= prim[j];
                while(b % prim[j] == 0)
                    b /= prim[j];
            }

            j++;
        }

        if(b > 1)
            d.push_back(b);

        int n = d.size();
        for(int i = 1; i < (1 << n); i++){
            prod = 1;
            nr = 0;
            for(int j = 0; j < n; j++){
                if((1 << j) & i){
                    prod *= d[j];
                    nr++;
                }
            }

            if(nr % 2)
                nr = 1;
            else
                nr = -1;

            ans += nr * (a / prod);
        }

        g << a - ans << '\n';
    }

    f.close();
    g.close();
}