#include<bits/stdc++.h>
#define int long long

using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

int t;

signed main(){
    fin >> t;
    while(t--){
        int a , b;
        fin >> a >> b;
        vector<int> div;
        int d = 2;
        while(b > 1){
            if(b % d == 0){
                div.push_back(d);
                while(b % d == 0) b /= d;
            }
            d++;
            if(d * d > b) d = b;
        }
        int cnt = 0 , lun = div.size();
        for(int mask = 1 ; mask < (1 << lun) ; mask++){
            int prod = 1 , cntbiti = 0;
            for(int i = 0 ; i < lun ; i++){
                if(mask & (1 << i)) prod *= div[i] , cntbiti++;
            }
            if(cntbiti % 2 == 1)  cnt += a / prod;
            else cnt -= a / prod;
        }
        fout << a - cnt << '\n';
    }
}