#include <bits/stdc++.h>
#define int long long
using namespace std;

ifstream fin("pinex.in");
ofstream fout("pinex.out");

const int VMAX = 1e6 + 2;

int a, b, m;
int ciur[VMAX];

signed main()
{
    vector<int> primes;
    ciur[1] = 1;
    for (int i = 2; i < VMAX; i++)
    {
        if (ciur[i] == 0)
        {
            primes.push_back(i);
            for (int j = i * i; j < VMAX; j += i)
            {
                ciur[j] = 1;
            }
        }
    }
    fin >> m;
    while (m--)
    {
        fin >> a >> b;
        vector<int> fact;
        int idx = 0;
        for (auto x : primes)
        {
            if(x * x > b)break;
            if (b % x == 0)
            {
                // cout << x << " ";
                fact.push_back(x);
                while(b % x == 0){
                    b /= x;
                } 
                idx++;
            }
        }
        if(b > 1){fact.push_back(b);idx++;}
        
        fact.resize(idx);
        // for(auto x: fact)
        // {
        //     cout << x << " ";
        // }
        cout << "\n";
        int ans = 0;
        for (int i = 1; i <= (1 << idx) - 1; i++)
        {
            int d = 1;
            for (int j = 0; j < idx; j++)
            {
                if (((i >> j) & 1) == 1)
                {
                    d *= fact[j];
                }
            }
            int bits = __builtin_popcount(i);
            if (bits % 2 != 0)
            {
                ans += a / d;
            }
            else
            {
                ans -= a / d;
            }
        }
        fout << a - ans << "\n";
    }
    return 0;
}