#include <cstdio>
        using namespace std;
        int a[1000001], nr;
        bool ok[1000001];
        bool verificare (int x)
        {
            int i;
            for (i=1; i<=nr; i++)
            {
                if (a[i]==x) return true;
            }
            return false;
        }
        void ciur (int n, int y)
        {
            int i, j;
            for (i=1; ((i*i)<<1)+(i<<1)<=n; i++)
            {
                if (ok[i]==false)
                {
                    for (j=((i*i)<<1)+(i<<1); (j<<1)+1<=n; j+=(i<<1)+1) ok[j]=true;
                }
            }
            if (y%2==0)
            {
                for (i=2; i<=n; i+=2) a[++nr]=i;
            }
            for (i=1; (i<<1)+1<=n; i++)
            {
                if (ok[i]==false && y%((i<<1)+1)==0)
                {
                    for (j=(i<<1)+1; j<=n; j+=(i<<1)+1)
                    {
                        if (verificare(j)==false)
                        {
                            a[++nr]=j;
                        }
                    }
                }
            }
        }
        int main()
        {
            int t, x, y, i;
            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;
                ciur(x,y);
                int s=x-nr;
                printf("%d\n",s);
            }
            fclose(stdin);
            fclose(stdout);
            return 0;
        }