#include <fstream>
#include <vector>
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
const int nmax = 1e6 + 1;
int sp[nmax] , q;
int arr[100];
vector <int> p;
int main()
{
    int pana = nmax - 1;
    for(int i = 2 ; i <= pana ; ++i)
    {
        if(!sp[i])
        {
            sp[i] = i;
            for(int j = i+i ; j <= pana ; j += i)
            {
                if(!sp[j]) sp[j] = i;
            }
            p.push_back(i);
        }
    }
    long long a , b;
    cin >> q;
    while(q--)
    {
        cin >> a >> b;
        int ind = 0;
        for(auto &it : p)
        {
            if(1LL*it*it > b || b <= pana) break;
            if(b%it) continue;
            arr[++ind] = it;
            while(b%it==0)
            {
                b/=it;
            }
        }
        while(b != 1)
        {
            int val = sp[b];
            arr[++ind] = val;
            while(b%val==0)
            {
                b/=val;
            }
        }
        long long ans = 0;
        int full = (1<<ind) - 1;
        for(int i = 1 ; i <= full ; ++i)
        {
            short int card = 0;
            long long prod = 1;
            for(int j = 0 ; j < ind ; ++j)
            {
                if(i&(1<<j))
                {
                    card++;
                    prod *= arr[j+1];
                }
            }
            if(card&1) ans -= a/prod;
            else ans += a/prod;
        }
        ans += a;
        cout << ans << '\n';
    }
	return 0;
}