#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define mod 1000000007
 
using namespace std;

ll prim[100100], cnt, A, B, d[500], M, rsp;
bool viz[1000100];

void make()
{
    int b = 1e6;
    for (int i = 2; i <= b; i++)
    {
        if (viz[i] == 0)
        { 
			prim[++cnt] = i;
			for (int j = i; j <= b; j += i)
				viz[j] = 1;
		}
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ifstream cin("pinex.in");
    ofstream cout("pinex.out");
    make();
    cnt = 0;
    cin >> M;
    while (M--)
    {
		cnt = 0; rsp = 0;
		cin >> A >> B;
		for (int i = 1; prim[i] <= sqrt(B); i++)
		{
			if (B % prim[i] == 0)
				d[cnt++] = prim[i];
			while (B % prim[i] == 0) B /= prim[i];
		}
		//for (int i = 0; i < cnt; i++) cout << d[i] << " ";
		
		if (B > 1) d[cnt++] = B;
		
		ll P = (1 << cnt);
		for (int i = 1; i < P; i++)
		{
			ll prod = 1, tmp = 0;
			for (int j = 0; j < cnt; j++)
				if (i & (1 << j)) prod *= d[j], tmp++;
			rsp += (tmp & 1 ? A / prod : -(A / prod));
		}
		cout << A - rsp << "\n";
    }
    return 0;
}