#include <bits/stdc++.h>
#define ull unsigned long long
#define FILES freopen("pinex.in","r",stdin);\
              freopen("pinex.out","w",stdout);
#define CMAX 15485863
#define fastio std::ios_base::sync_with_stdio(NULL),cin.tie(NULL),cout.tie(NULL);
#define mp make_pair
#define INF 1e18
#define mod 1000003
#define ll long long
#define SMAX 300
#define MAX 1000000
#define pb push_back
#define add emplace_back
#define void inline void

using namespace std;
int t,a,b;
bool ciur[MAX+5];
vector<int>primes;
int main()
{
    fastio
    FILES
    ciur[0] = ciur[1] = 1;
    primes.add(2);
    for(int i = 4;i <= MAX; i += 2) ciur[i] = 1;
    for(int i = 3;i <= MAX;i += 2)
    {
        if(!ciur[i])
        {
            primes.add(i);
            for(int j = i + i + i;j <= MAX; j += i << 1) ciur[j] = 1;
        }
    }
    cin >> t;
    while(t--)
    {
        cin >> a >> b;
        vector<int> v;
        int z = b;
        for(int i = 0;i < primes.size() && primes[i] * primes[i] <= b; ++i)
        {
            int cnt = 0;
            while(!(b%primes[i])) b /= primes[i],cnt++;
            if(cnt) v.add(primes[i]);
        }
        if(b!=1) v.add(b);
        int ans = a;
        for(int i = 0;i < v.size(); ++i) ans -= a / v[i];
        int x = v.size();
        x = (1 << x) - 1;
        map<int,int>Mp;
        for(int i = 1;i <= x; ++i)
        {
            int r = __builtin_popcount(i);
            if(r == 1)
            {
                int cnt = -1;
                for(int j = 1;j <= i; j *= 2)
                {
                    cnt++;
                    if(i & j)
                    {
                        Mp[i] = v[cnt];
                        break;
                    }
                }
                continue;
            }
            int cnt = -1;
            for(int j = 1;j <= i; j *= 2)
            {
                cnt++;
                if(i & j)
                {
                    int u = i ^ j;
                    Mp[i] = Mp[u] * v[cnt];
                    break;
                }
            }
            if(Mp[i] == z) ans -= a / Mp[i];
            else ans += a / Mp[i];
        }
        cout << ans << '\n';
    }
}