#ifndef LOCAL
    #pragma GCC optimize("Ofast")
#endif

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
using ll = long long;
using ci = const int;
using cll = const long long;

using namespace std;

const int SQRT_MAX = 1e6 + 5;
/*******************************/
// INPUT / OUTPUT

#ifndef LOCAL
    ifstream in("pinex.in");
    ofstream out("pinex.out");
    #define cin in
    #define cout out
#endif
/*******************************/
/// GLOBAL DECLARATIONS

int T;
int N;
ll A, B;
ll rasp;
bool ciur[SQRT_MAX];

vector <int> prime, div_primi;
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    cin >> T;
}
///-------------------------------------
inline void Reset()
{
    rasp = 0;
    div_primi.clear();
}
///-------------------------------------
inline void Read()
{
    cin >> A >> B;
}
///-------------------------------------
inline vector <int> get_prime_divs(ll nr)
{
    vector <int> res;
    for (auto x: prime)
    {
        if (nr % x == 0)
        {
            res.push_back(x);
            while (nr % x == 0)
                nr /= x;
        }
    }

    if (nr != 1)
        res.push_back(nr);

    return res;
}
///-------------------------------------
inline void Solve()
{
    div_primi = get_prime_divs(B);

    N = div_primi.size();
    int masca_max = (1 << N), semn;

    ll intersectie;
    for (int mask = 1 ; mask < masca_max ; ++ mask)
    {
        semn = -1;
        intersectie = 1;

        for (int bit = 0 ; bit < N ; ++ bit)
        {
            if (mask & (1 << bit))
            {
                intersectie *= div_primi[bit]; 
                semn *= -1;
            }
        }

        rasp += semn * (A / intersectie);
    }

    rasp = A - rasp;
}
///-------------------------------------
inline void Output()
{
    cout << rasp << "\n";
}
///-------------------------------------
inline void TestCase()
{
    Reset();
    Read();
    Solve();
    Output();
}
///-------------------------------------
inline void Solution()
{
    ll prod;
    for (int i = 2 ; i < SQRT_MAX ; ++ i)
    {
        if (ciur[i]) continue;

        prime.push_back(i);
        prod = 1LL * i * i;
        if (prod >= SQRT_MAX) continue;
        for (int j = i * i ; j < SQRT_MAX ; j += i)
        {
            ciur[j] = true;
        }
    }

    while (T --)
    {
        TestCase();
    }
}
///-------------------------------------
int main()
{
    #ifndef LOCAL
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif
    ReadInput();
    Solution();
    return 0;
}