#include<cstdio>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<bitset>
#include<deque>
#include<queue>
#include<set>
#include<map>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<unordered_map>

#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

const int pmax = 1000005;

int i, cnt, q, lim, j, g, t, f[105], p[pmax / 10];
long long a, b, nr, sol;

bitset<pmax> viz;

int main()
{
    freopen("pinex.in", "r", stdin);
    freopen("pinex.out", "w", stdout);

    p[++q] = 2;
    lim = 1000000;

    for(i = 3; i * i <= lim; i += 2)
        if(!viz[i])
        {
            p[++q] = i;
            for(j = i * i; j <= lim; j += i * 2)
                viz[j] = 1;
        }

    for(; i <= lim; i += 2)
        if(!viz[i])
            p[++q] = i;

    scanf("%d", &t);

    for(; t; t--)
    {
        scanf("%lld%lld", &a, &b);

        g = -1;
        for(i = 1; i <= q && 1LL * p[i]*p[i] <= b; i++)
            if(b % p[i] == 0)
            {
                f[++g] = p[i];
                while(b % p[i] == 0) b /= p[i];
            }
        if(b > 1) f[++g] = b;

        g++;
        lim = 1 << g;
        sol = 0;

        for(i = 1; i < lim; i++)
        {
            cnt = 0;
            nr = 1;

            for(j = 0; j < g; j++)
                if((1 << j) & i)
                {
                    cnt++;
                    nr *= f[j];
                }

            if(cnt & 1) sol += a / nr;
            else sol -= a / nr;
        }

        printf("%lld\n", a - sol);
    }
    return 0;
}