#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, ind, 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;
            ind = 0;
            j = i;
            while(j > 0){
                if(j % 2)
                    prod *= -d[ind];

                j /= 2;
                ind++;
            }

            ans += a / prod;
        }

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

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