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

public class Solution {
    public int ways(int N, int K) {
        int[] f = new int[K+1];
        int[] ff = new int[K+1];
        int[] cur = null;
        for (int i = N-1; i >= 0; i--) {
            if (i == N - 1) cur = ff;
            else if (i == N - 2) cur = f;
            else cur = new int[K+1];
            for (int j = 0; j <= K; j++) {
                if (j == 0) cur[j] = 1;
                else if (i == N - 1) {
                    cur[j] = j == 1 ? 1 : 0;
                    continue;
                } else if (i == N - 2) {
                    cur[j] = j == 1 ? 2 : 0;
                    continue;
                } else {
                    cur[j] = (ff[j-1] + f[j]) % 100003;
                }
            }
            if (i < N-2) {
                ff = f;
                f = cur;
            }
        }
        return cur[K];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            long N = sc.nextLong();
            long K = sc.nextLong();
            System.out.println(new Solution().ways((int)(N % 100003), (int)(K % 100003)));
        }
    }
}