import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {
    
    static int N, K;
    static HashMap<String,Integer> map ;
    public static void main(String[] args) {
        Solution s = new Solution();
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        int T = Integer.parseInt(in.nextLine());
        while(T>=1){
          
            map = new HashMap();
            String[] ips = in.nextLine().split(" ");
            N = Integer.parseInt(ips[0]); K = Integer.parseInt(ips[1]);           
            System.out.println(s.fn(K, 1)%100003);
            T--;
        }
    }
    int fn(int k, int i){          
            if(map.get(k+" "+i)!=null)
                return map.get(k+" "+i);
            if(k==0){
                return 1;
            }
            if(i>=N+1)
                return 0;
            if(map.get(k+" "+i)==null)
                map.put((k-1)+" "+(i+2),fn(k-1, i+2));//taken this i
             if(map.get(k+" "+i)==null)
                map.put((k)+" "+(i+1),fn(k, i+1));//not taken this i
            return map.get((k-1)+" "+(i+2)) + map.get((k)+" "+(i+1));
        }
}