#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NMAX 1000000
#define KMAX 7
#define SQRTNMAX 1000
#define PRIME 0
#define CNT   1

int T, N, K, i, j, jj, a, b, ind;
int part[NMAX+5];
int prim[NMAX+5], k_prim[KMAX+1][NMAX+5], cnt[KMAX+1];

int cmp(const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}

void ciur()
{
    for (i = 2; i <= SQRTNMAX; i++)
        if (!prim[i])
        {
            prim[i]++;
            part[i] = i;
            k_prim[prim[i]][++cnt[prim[i]]] = i;
            for (j = i<<1; j <= NMAX; j += i)
            {
                prim[j]++;
                
                if (!part[j])
                {
                    
                    part[j] = 1;
                }
                jj = j;
                while (jj && jj%i == 0)
                {
                    
                    part[j] *= i;
                    jj /= i;
                }
                
                //if (j == 48)
                //    printf("%d\n", part[j]);
                    
                if (part[j] == j)
                    k_prim[prim[j]][++cnt[prim[j]]] = j;
            }
        }

    /*for (i = 5000; i <= 6000; i++)
        if (part[i] != i)
        {
            printf("i = %d    part[i] = %d\n", i, part[i]);
            //break;
        }*/
    //        k_prim[prim[i]][++cnt[prim[i]]] = i;
    k_prim[0][++cnt[prim[0]]] = 1;

    for (i = 1; i <= KMAX; i++)
    //    qsort(&k_prim[i][1], cnt[i], sizeof(int), cmp);
        printf("%d\n", cnt[i]);
}


int srch(int a, int b, int nr, int k)
{
    int mid = (a + b)>>1;

    if (a == b)
    {
        if (k_prim[k][a] == nr) 
            return a-1;
        else if (k_prim[k][a] < nr)
            return a;
        else
            return a-1;
    }

    if (k_prim[k][mid] < nr)
        return srch(mid+1, b, nr, k);
    else if (k_prim[k][mid] > nr)
        return srch(a, mid-1, nr, k);
    else
        return mid-1;
}


int main()
{
    FILE *in, *out;
    in =  fopen("divprim.in", "r");
    out = fopen("divprim.out", "w");
    fscanf(in, "%d\n", &T);
    
    ciur();

    while(T)
    {
        fscanf(in, "%d %d\n", &N, &K);
        if (K == 0)
            fprintf(out, "%d\n", 1);
        else if (N <= k_prim[K][1])
            fprintf(out, "%d\n", 0);
        else
        {
            //ind = srch(1, cnt[K], N, K);
            //fprintf(out, "%d\n", k_prim[K][ind]);
            fprintf(out, "%d\n", 1);
        }
        T--;
    }


    fclose(in);
    fclose(out);
    return 0;  
}