from sys import *

buf = {(1,1):1,(0,1):0,(0,0):1,(1,0):1}

def g(N, K):
	global buf
	""" the evil recursive function
	"""
	key = (N,K)
	if N < 0 or K < 0:
		return 0
	if key in buf:
		return buf[key]
	else:
		if N == 2 * K - 1:
			buf[key] = 1
			
		elif N < 2 * K - 1:
			buf[key] = 0
		else:
			buf[key] = g(N - 1, K) + g(N - 2, K - 1)
	return buf[key]

if __name__ == '__main__':
	line = stdin.readline()

	T = int(line)

	for i in range(T):
		scheme = stdin.readline()

		N = int(scheme.split()[0])
		K = int(scheme.split()[1])

		if N < 2 * K - 1:
			print 0
		else:
			for n in range(N):
				for k in range(n/2 + 1):
					g(n+1,k+1)
			print buf[(N,K)] % 100003