/*
 * ICPC Greater NY Regional Contest, Nov 18, 2018
 * Hedwig's Ladder solution by Fred Pickel, C-Scape Consulting Corp
 */
#include <stdio.h>
#include <ctype.h>
#include <math.h>

#define MAX_N	1000
#define N_BASE	10007

/*
 * Any path eith ends in an edge that was verical or moved right to the final vertex or moved left
 * to the final vertex.
 * Let p_v[n] = number of paths of length n which end in a vertical edge
 *		p_rt[n] = number of paths of length n which end in a right moving edge
 *		p_lft[n] = number of paths of length n which end in a left moving edge
 * Since no vertex can be visited twice, left moving edges can only occur ate the end of the path
 * If a path ends in a left moving edge then in must consist of a path of (n-2k-1) right or vertical edges
 *	ending in a right edge followed by k >= 1 right edges, a vertical edge, and then k left edges
 * so p_lft[n] = SUM(k = 1..(n-3)/2) p_rt[n-2k-1] = p_lft[n-2] + p_rt[n-3]
 * 
 * if a path ends in a vertical edge, the previous edge must be a right edge so
 *		p_v[n] = p_rt[n-1]
 * if a path ends in a right edge the the previous edge can be right or vertical so
 *		p_rt[n] = p_rt[n-1] + p_v[n-1] = p_rt[n-1] + p_rt[n-2]
 * p_rt[1] = p_v[1] = 1 p_lft[1] = 0 p_rt[2] = 2 p_v[2] = 1 p_lft[2] = 0 
 * p_rt[3] = 3 p_v[3] = 2 p_lft[3] = 1 
 * total paths of length n = p_v[n] + p_rt[n] + p_lft[n]
 */
int p_rt[MAX_N + 1], p_v[MAX_N + 1], p_lft[MAX_N + 1];
int last_n = 0;

int Find_Paths(int nval)
{
	int i;
	if(nval > last_n) {
		for(i = last_n+1 ; i <= nval ; i++) {
			p_lft[i] = (p_lft[i-2] + p_rt[i - 3])  % N_BASE;
			p_rt[i] = (p_rt[i-1] + p_v[i-1])  % N_BASE;
			p_v[i] = p_rt[i-1] % N_BASE;
		}
		last_n = nval;
	}

	return ((p_v[nval] + p_rt[nval] + p_lft[nval]) % N_BASE);
}

char inbuf[256];
int main()
{
	int nprob, curprob, ret, index, count;
	if(fgets(&(inbuf[0]), 255, stdin) == NULL)
	{
		fprintf(stderr, "Read failed on problem count\n");
		return -1;
	}
	if(sscanf(&(inbuf[0]), "%d", &nprob) != 1)
	{
		fprintf(stderr, "Scan failed on problem count\n");
		return -2;
	}
	p_rt[1] = p_v[1] = 1; p_lft[1] = 0; p_rt[2] = 2; p_v[2] = 1; p_lft[2] = 0;
	p_rt[3] = 3; p_v[3] = 2; p_lft[3] = 1;
	last_n = 3;

	for(curprob = 1; curprob <= nprob ; curprob++)
	{
		if(fgets(&(inbuf[0]), 255, stdin) == NULL)
		{
			fprintf(stderr, "Read failed on problem %d header\n", curprob);
			return -3;
		}
		if(sscanf(&(inbuf[0]), "%d %d", &index, &count) != 2) {
			fprintf(stderr, "scan failed on problem %d \n", curprob);
			return -4;
		}
		if(index != curprob) {
			fprintf(stderr, "problem index %d not = expected problem %d\n",
				index, curprob);
			return -5;
		}
		if(count > MAX_N) {
			fprintf(stderr, "problem index %d count %d > max %d\n",
				index, count, MAX_N);
			return -6;
		}
		ret = Find_Paths(count);
		printf("%d %d\n", curprob, ret);
	}
	return 0;
}