#include <iostream>
#include <fstream>
#include <math.h>
#include <string.h>
#include <algorithm>

using namespace std;

ifstream f ("pinex.in");
ofstream g ("pinex.out");

#define NMAX 1000001
long long m,a,b,fact[30];
int fprim[80001];
bool prim[NMAX];

void ciur()
{
    long i,j;
    for (i=2;i<=NMAX;i++)
       prim[i]=1;
    for (i=2;i<=NMAX;i++)
       if (prim[i])
       {
        for (j=2*i;j<=NMAX;j+=i)

           prim[j]=0;
           fprim[++fprim[0]]=i;
       }
    }

void solve()
{
    long long t=0,d=0;
    while (b>1)
    {
        d++;
        if (b%fprim[d]==0)
        {
            fact[++t]=fprim[d];
            while (b%fprim[d]==0)
                 b/=fprim[d];
            }
        if (fprim[d]>sqrt(b) && b>1)
        {
            fact[++t]=b;
            b=1;
        }
    }
    long long sol=a;
    int i;
    for (i=1;i<(1<<t);i++)
    {
        long long nr=0,prod=1;
        int j;
        for (j=0;j<t;j++)
            if ((1<<j)& i)
        {
            prod=1LL*prod*fact[j+1];
            nr++;
        }
        if (nr%2)
            nr=-1;
        else
            nr=1;
        sol=sol+1LL*nr*a/prod;
    }
        g<<sol<<'\n';
    }


int main()
{
    ciur();
    f>>m;
    for (int i=1;i<=m;i++)
    {
        f>>a>>b;
        solve();
    }
    f.close();
    g.close();
    return 0;
}