#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pd pair<double,double>
#define ld long double
#define pld pair<ld,ld>
#define lg length()
#define sz size()
#define pb push_back
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005
#define x1 xdddddddddddddddddd
#define y1 ydddddddddddddddddd

int m,s=1e6,t,q[1000005];

ll a,b,ans;

vector <ll> p,w;

int main(){
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");
    cin >> m;
    for(int i=2;i<=s;i++){
        if(!q[i]){
            w.pb(i);
            for(int j=i;j<=s;j+=i) q[j]=1;
        }
    }
    for(int i=1;i<=m;i++){
        cin >> a >> b;
        t=0; p.clear();
        for(int j : w){
            if(b%j==0) p.pb(j);
            while(b%j==0) b/=j;
        }
        if(b!=1) p.pb(b);
        t=p.sz; ans=0;
        for(int j=1;j<(1<<t);j++){
            ll x=1,y=0;
            for(int k=0;k<t;k++){
                if((1<<k)&j) x*=p[k],y++;
            }
            x=a/x;
            if(y%2==0) x*=-1;
            ans+=x;
        }
        cout << a-ans << '\n';
    }
}