#include <bits/stdc++.h>
#define cin ci
#define cout co
#define int long long
using namespace std;
ifstream cin("pinex.in");
ofstream cout("pinex.out");
const int Cmax = 1000001;
vector<int> divs;
int m, a, b;

bitset <Cmax> prime;
void ciur()
{
    prime[0] = prime[1] = 1;
    for(int i=4; i<=Cmax; i+=2)
        prime[i] = 1;
    for(int i=3; i<=1000; i+=2)
        if(prime[i] == 0)
            for(int j=i*i; j<=Cmax; j+=i)
                prime[j] = 1;


}
/*int solve()
{
    int sum = 0;
    int endi = divs[b];
    for(int mask = 1; mask <(endi); mask++)
        //for(int i)
      //  if(mask & (1 << ))
}*/
int solve1 (int n, int r)
{
    vector<int> p;
    for (int d=2; d*d<=n; d++)
        if (n % d == 0)
        {
            p.push_back(d);
            while(n % d == 0)
                n /= d;
        }
    if (n > 1)
        p.push_back(n);

    int sum = 0;
    int endi = 1 << p.size();
    for (int mask = 1; mask < endi; mask++)
    {
        int mult = 1,
            bits = 0;
        for (int i=0; i<endi; i++)
            if (mask & (1<<i))
            {
                bits++;
                mult *= p[i];
            }

        int cur = r / mult;
        if (bits % 2 == 1)
            sum += cur;
        else
            sum -= cur;
    }

    return r - sum;
}
int32_t main()
{
    cin >> m;
    while(m--)
    {
        cin >> a >> b;
        cout << solve1(b, a) << '\n';
    }
    return 0;
}