testsLeft = int(input().strip())

def touchingTest(l):
    for i in range(1,len(l)):
        if l[i] and l[i-1]: return False
    return True

while testsLeft > 0:
    testsLeft -= 1
    n, k = tuple(int(i) for i in input().strip().split(' '))
    possibilities = [[True],[False]]
    while n > 1:
        buf = []
        for p in possibilities:
            buf.append(p + [True])
            buf.append(p + [False])
        n -= 1
        possibilities = buf
    possibilities = [p for p in possibilities if p.count(True) == k and touchingTest(p)]
    print(len(possibilities) % 100003)