#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;
}
}