# Enter your code here. Read input from STDIN. Print output to STDOUT
from math import ceil
from operator import mul
from fractions import Fraction


cache = {}
def ways_to_cheat(N, k):
    if cache.has_key(str(N)+" "+str(k)):
        return cache[str(N)+" "+str(k)]
    #print N,k
    if N<k:
        return 0
    elif k==1:
        return N%100003
    elif k == 2:
        return ((N*(N-1)/2)-N+1)%10003
    elif N==k:
        return 0
    else:
        if (k>1):
            cache[str(N)+" "+str(k)] = (ways_to_cheat(N-2,k-1)+ways_to_cheat(N-1,k))%100003
            return cache[str(N)+" "+str(k)]
        else:
            return 0
def nCk(n,k): 
    return int( reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1) )
    
def best_way_to_cheat(N,k):
    num = N-k+1
    if num < k:
        return 0
    else:
        return nCk(num,k)%100003
    
tests = int(raw_input())
for i in range(tests):
    inp = raw_input()
    N,k = [int(inp.split()[0]), int(inp.split()[1])]
    print best_way_to_cheat(N,k)%100003 
    array = []