#include <cstdio>
        using namespace std;
        int cmmdc (int a, int b)
        {
            int r, x, y=1;
            x=a;
            y=b;
            r=x%y;
            while (r>0)
            {
                x=y;
                y=r;
                r=x%y;
            }
            return y;
        }
        int main()
        {
            int t, i, j, x, y, z, nr;
            freopen("pinex.in","r",stdin);
            freopen("pinex.out","w",stdout);
            scanf("%d",&t);
            for (i=1; i<=t; i++)
            {
                scanf("%d%d",&x,&y); nr=0;
                for (j=1; j<=x; j++)
                {
                    z=cmmdc(j,y);
                    if (z==1) nr++;
                }
                printf("%d\n",nr);
            }
            fclose(stdin);
            fclose(stdout);
            return 0;
        }