#include <fstream>
#include <cmath>
#include <iostream>
#define int long long
using namespace std;
ifstream f("pinex.in");
ofstream g("pinex.out");
int ciur[1000009], prime[100009], q[50], p[50];
signed main ()
{
    ciur[0]=ciur[1]=1;
    for (int i=4; i<=1000000; i+=2)
        ciur[i]=1;
    for (int i=3; i*i<=1000000; i+=2)
    {
        if (!ciur[i])
        {
            for (int j=2*i; j<=1000000; j+=i) ciur[j]=1;
        }
    }
    int cnt=0;
    for (int i=1; i<=1000000; i++)
        if (!ciur[i]) prime[++cnt]=i;
    int m;
    f >> m;
    while (m--)
    {
        int a, b, l=0, ans=0;
        f >> a >> b;
        int r=sqrtl(b), i=1;
        while (i<=cnt && b!=1 && prime[i]<=r)
        {
            if (b%prime[i]==0)
            {
                p[++l]=prime[i];
                while (b%prime[i]==0) b/=prime[i];
            }
            i++;
        }
        if (b!=1) p[++l]=b;
        for (int i=0; i<=l; i++)
        {
            q[i]=0;
        }
        while (!q[0])
        {
            int x=1, y=0;
            for (int i=1; i<=l; i++)
            {
                if (q[i]==1)
                {
                    x*=p[i];
                    y++;
                }
            }
            if (y%2) ans-=a/x;
            else ans+=a/x;
            q[l]++;
            int cl=l;
            while (q[cl]==2)
            {
                q[cl]=0;
                q[cl-1]++;
                cl--;
            }
        }
        g << ans <<'\n';
    }
}