#include <cstdio>
#include <string.h>
using namespace std;
int fr[1000000], div[1000000], k=0, a, b, x;
FILE* F=freopen("pinex.in", "r", stdin);
FILE* G=freopen("pinex.out", "w", stdout);
struct sfij
{
    int val=1;
    bool par=0;
} prod[1000000];

void ciur()
{
    for(int i=2; i<1000000; i++)
        fr[i]=1;
    for(int i=2; i<1000000; i++)
        if(fr[i]==1)
            for(int j=2*i; j<1000000; j+=i)
                fr[j]=0;
    return;
}

void submultimi(int n)
{
    x=-1;
    int v=(1<<n);
        for(int nr=1; nr<v; nr++)
        {
            x++;
            for(int j=0; j<n; j++)
                if(nr&(1<<j))
                {
                    prod[x].val*=div[j];
                    switch(prod[nr].par)
                    {
                        case 0:
                        {
                            prod[x].par=1;
                            break;
                        }
                        case 1:
                        {
                            prod[x].par=0;
                            break;
                        }
                    }
                }
        }
        return;
}

int main()
{
    ciur();
    int n;
    scanf("%d\n", &n);
    for(int m=0; m<n; m++)
    {
        k=0; int sol=0;
        scanf("%d %d\n", &a, &b);
        for(int i=2; i<=b; i++)
        {
            if(fr[i]==1&&b%i==0)
                div[k++]=i;
        }
        submultimi(k);
        for(int i=1; i<=k; i++)
        {
            if(prod[i].val>1)
            {
                if(prod[i].par==1)
                    sol-=prod[i].val;
                else
                    sol+=prod[i].val;
            }
        }
        printf("%d\n", sol);
    }
    return 0;
}