#include <bits/stdc++.h>
#define ll int64_t
using namespace std;
#if 1
ifstream fin("pinex.in");
ofstream fout("pinex.out");
#define cin fin
#define cout fout
#endif // 1
int a,b;
const ll nmx = 1e6 + 3;
int era[nmx]; /// 1 - neprim
vector<int> pr;
void calcEras(){
    for(ll i=4;i<nmx;i+=2)
        era[i] = 1;
    era[0] = era[1] = 1;
    for(ll i=3;i<nmx;i+=2)
        if(era[i] == 0)
            for(ll j=i*i;j<nmx;j+=i)
                era[j] = 1;
    for(ll i=0;i<nmx;i++)
        if(era[i] == 0){
            pr.push_back(i);
        }
}

vector<int> dec(int x){
    vector<int> v;
    int i = 0;
    while(pr[i]*pr[i]<=x){
        if(x%pr[i]==0){
            v.push_back(pr[i]);
            do
                x /= pr[i];
            while(x%pr[i]==0);
        }
        i++;
    }
    if(x!=1){
        v.push_back(x);
    }
    return v;
}

void solve(){
    cin >> a >> b;
    auto divs = dec(b);
    int ans = 0;
    for(int msk=1;msk<(1<<divs.size());msk++){
        int nr = 1,cnt = 0;
        for(int j=0;j<divs.size();j++)
            if((1<<j)&msk)
                cnt++, nr*=divs[j];
        ans += (cnt&1 ? 1 : -1) * a / nr;
    }
    cout << a-ans << "\n";

}

int main()
{
    calcEras();
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}