#include <stdio.h>

#define in "divprim.in"
#define out "divprim.out"

int ndp[] = { 
0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 
1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 
2, 2, 1, 2, 1, 2, 1, 2, 1, 3, 
1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 
1, 3, 1, 2, 2, 2, 1, 2, 1, 2, 
2, 2, 1, 2, 2, 2, 2, 2, 1, 3, 
1, 2, 2, 1, 2, 3, 1, 2, 2, 3, 
1, 2, 1, 2, 2, 2, 2, 3, 1, 2, 
1, 2, 1, 3, 2, 2, 2, 2, 1, 3, 
2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 
1, 3, 1, 2, 3, 2, 1, 2, 1, 3, 
2, 2, 1, 3, 2, 2, 2, 2, 2, 3, 
1, 2, 2, 2, 1, 3, 1, 1, 2, 3, 
1, 3, 2, 2, 2, 2, 1, 3, 1, 3, 
2, 2, 2, 2, 2, 2, 2, 2, 1, 3, 
1, 2, 2, 3, 2, 3, 1, 2, 2, 2, 
2, 2, 1, 2, 3, 2, 1, 3, 1, 3, 
2, 2, 1, 3, 2, 2, 2, 2, 1, 3, 
1, 3, 2, 2, 2, 3, 2, 2, 2, 3 
};

#define NMAX 180

int T;
int sol[NMAX][8];

void Read();
void Dinamic();

FILE *fout = fopen( out, "w" );

int main()
{
    Dinamic();
    Read();
    
    /*fprintf( fout, "\n" );
    int i, j;
    for ( i = 1; i <= NMAX; ++i )
    {
        for ( j = 1; j <= 7; ++j )
        {
            fprintf( fout, "%d ", sol[i][j] );
        }
        fprintf( fout, "\n" );
    }
    */
    fclose( fout );
    return 0;
}

void Read()
{
     FILE *fin = fopen ( in, "r" );
     fscanf( fin, "%d", &T );
     int i, n, k;
     for ( i = 1; i <= T; ++i ) 
     {
         fscanf( fin, "%d%d", &n, &k );
         fprintf( fout, "%d\n", sol[n][k] );
     }
     
     fclose( fin );
}


void Dinamic()
{
     int i, j;
     for ( i = 1; i <= 7; ++i )
     {
         sol[1][i] = 0;
     }
     
     for ( i = 2; i <= NMAX; ++i )
     {
         for ( j = 1; j <= 7; ++j ) sol[i][j] = sol[i-1][j];
         sol[i][ndp[i-1]] = i;
     }
}