#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++){
        if(!np[i]){
            for(int j = 2 * i; j < N; j += i)
                np[j] = 1;
        }
    }

    f >> t;
    while(t--){
        f >> a >> b;
        ans = a;
        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(b > 1)
            d.push_back(b);

        int n = d.size();
        for(int i = 1; i < (1 << n); i++){
            prod = 1;
            int 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();
}