package main

import (
    "fmt"
    //"strconv"
    //"strings"
)

func getSol(n uint64,k uint64, m [][]int64) int64 {
    /*
    keys := []string{strconv.FormatUint(n,10),strconv.FormatUint(k,10)};
    key := strings.Join(keys,".");
    _, ok := m[key]
    if !ok {
        if k == 1 {
            m[key] = int64(n) % 100003
        } else if k > (n+1)/2 {
            m[key] = 0
        } else {
            m[key] =( getSol(n-2,k-1,m) + getSol(n-1,k,m) ) % 100003
        }
    }
    return m[key]
    */
    if m[n-1][k-1] == -1 {
        if k == 1 {
            m[n-1][k-1] = int64(n) % 100003
        } else if k > (n+1)/2 {
            m[n-1][k-1] = 0
        } else {
            m[n-1][k-1] =( getSol(n-2,k-1,m) + getSol(n-1,k,m) ) % 100003
        }
    }
    return m[n-1][k-1]
}
func main() {
    T := readInt()
    var N []uint64 = make([]uint64, T)
    var K []uint64 = make([]uint64, T)
    for i := 0; i < T; i++ {
        fmt.Scanf("%d %d\n", &N[i], &K[i])
    }
    for i := 0; i < T; i++ {
        
        picture := make([][]int64, N[i])
        for k := range picture {
	        picture[k] = make([]int64, K[i])
	        for j := range picture[k] {
                picture[k][j] = -1
            }
        }
        //picture := make(map[string]int64)
        
        sol := getSol(N[i],K[i], picture) % 100003
        /*for h:=uint64(0); h<N[i]; h++ {
            for l:=uint64(0); l<K[i];l++ {
                fmt.Println(picture[h][l])
            }
        }*/
        fmt.Println(sol)
    }
}

func readInt() int {
    var n int
    _, err := fmt.Scanf("%d\n", &n)

    if err != nil {
        panic(err)
    }

    return n
}