#include <bits/stdc++.h>
using namespace std;
ifstream fin("pinex.in");
ofstream fout("pinex.out");
#define cin fin
#define cout fout
int q;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> q;
    while(q--){
        long long a, b, ans = 0;
        cin >> a >> b;
        vector<int> prime;
        int d = 2, p = 1;
        while(b > 1){
            p = 0;
            while(b && b % d == 0){
                b /= d;
                p++;
            }
            if(p){
                prime.push_back(d);
            }
            d++;
            if(d *d > b && b > 1){
                d = b;
            }
        }
        
        int s = prime.size();
        for(int mask = 1; mask < (1 << s); mask++){
            long long sm = 1;
            for(int i = 0; i < s; i++){
                if(mask & (1 << i)){
                    sm = 1ULL * sm * prime[i];
                }
            }
            if(sm <= a){
                if(__builtin_popcount(mask) % 2 == 0){
                    ans -= (a / sm);
                }else{
                    ans += (a / sm);
                }
            }
        }
        cout << a - ans << '\n';
    }
}