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

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

const int BMAX = 1e6 + 2;
int ciur[BMAX];

signed main()
{
    
    vector<int> primes;
    for(int i = 2; i < BMAX; i++)
    {
        if(ciur[i] == 0){
            primes.push_back(i);
            for(int j = 2*i; j < BMAX; j += i)
            {
                ciur[j] = 1;
            }
        }
    }
    
    int t;
    fin >> t;

    while(t--)
    {
        int a, b;
        fin >> a >> b;
        
        vector<int> fact;
        int idx = 0;
        while(b > 1 && (primes[idx] * primes[idx]) <= b)
        {
            int p = 0;
            while(b % primes[idx] == 0)
            {
                p++;
                b /= primes[idx];
            }

            if(p)
            {
                fact.push_back(primes[idx]);
            }
            idx++;
        }
        if(b > 1)
        {
            fact.push_back(b);
        }

        int ans = 0, nrf = fact.size();
        for(int mask = 1; mask < (1 << nrf); mask++)
        {
            int prod = 1;
            int cnt = 0;
            for(int i = 0; i < nrf; i++)
            {
                int bt = (mask >> i) & 1;
                if(bt)
                {
                    prod *= fact[i];
                    cnt++;
                }
            }
            
            if(cnt % 2 == 0)
            {
                ans -= a / prod;
            }
            else{
                ans += a / prod;
            }
        }
        fout << a - ans << "\n";
    }
    return 0;
}