t = int(raw_input())

def f(n,k):
	if k==0 or n==0:
		return 0
	if k==1:
		return n
	if n==k:
		return 0
	if k > n:
		return 0
		
	return  (f(n-1, k) + f(n-2, k-1))



for i in range(t):
	n,k = raw_input().split(' ')
	n = int(n)
	k = int(k)
	
	lovers = [[0 for x in xrange(k+1)] for x in xrange(n+1)]
	
	for i in range(1,n+1):
		lovers[i][1] = i
	
	
	for i in range(2,k+1):
		for j in range(i+1,n+1):
			lovers[j][i] = lovers[j-1][i]+lovers[j-2][i-1]
	
	#for i in lovers:
	#	print i
	
	print lovers[n][k]%100003
	
	
	#print f(n,k)