#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e6 + 1;
short t;
long long a, b, prod, ans, nr = 0;
bitset<N> np;

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

    f >> t;
    while(t--){
        f >> a >> b;
        ans = 0;
        vector<long long> d;
        for(int i = 2; i * i <= b; i++){
            if(!np[i] && b % i == 0){
                d.push_back(i);
                b /= i;
                while(b % i == 0)
                    b /= i;
            }
        }

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

        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();
}