def combHelp(top,bottom):
    end =1
    while top>bottom:
        end *= top
        top-=1
    return end

def visit(n,k):
    return combHelp(n-k+1,n-2*k+1)//combHelp(k,1)%100003
    
for _ in range(int(input())):
    print(visit(*map(int,input().split())))