#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#pragma GCC optimize ("O1")
#pragma GCC optimize ("O2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")

using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree <long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update>
#define lsb(x)(x & (-x))

const long long max_size = 1e6 + 20;

bool ciur[max_size];
vector <long long> pr;

void solve ()
{
    long long a, b;
    cin >> a >> b;
    vector <long long> divz;
    for (auto f : pr)
    {
        if (b < f)
        {
            break;
        }
        if (b % f != 0)
        {
            continue;
        }
        divz.push_back(f);
        while (b % f == 0)
        {
            b /= f;
        }
    }
    if (b != 1)
    {
        divz.push_back(b);
    }
    long long ans = 0;
    for (long long i = 1; i < (1 << divz.size()); i++)
    {
        long long val = -1;
        for (long long j = 0; j < divz.size(); j++)
        {
            if ((i & (1 << j)) != 0)
            {
                val *= -divz[j];
            }
        }
        ans += a / val;
    }
    cout << a - ans;
    cout << '\n';
}

void ciuru ()
{
    for (long long i = 2; i < max_size; i++)
    {
        if (ciur[i] == 1)
        {
            continue;
        }
        pr.push_back(i);
        for (long long j = 2 * i; j < max_size; j++)
        {
            ciur[j] = 1;
        }
    }
}

signed main ()
{
    ciuru();
#ifdef LOCAL
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#else
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);
#endif // LOCAL
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long tt;
    cin >> tt;
    //tt = 1;
    while (tt--)
    {
        solve();
    }
    return 0;
}