def solve(n, k):
	j = -1
	if k < n - k: j = k
	else: j = n - k
	p = q = 1
	for i in xrange(k):
		p *= n - i
		q *= 1 + i
	return p / q


t = int(raw_input())
while t:
	t -= 1
	n, k = [int(x) for x in raw_input().split()]
	ans = solve(n - k + 1, k) % 100003
	print ans