import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Locale;

/**
 * Created by smenedi on 10/3/14.
 */
public class Solution {
    private BufferedReader in;
    private static final int MODULO = 100003;

    public void run() throws IOException {
        in = new BufferedReader(new InputStreamReader(System.in));
        int iNumberofTests = Integer.parseInt(in.readLine());
        long[] x = new long[iNumberofTests];
        long[] y = new long[iNumberofTests];

        for (int t = 0; t < iNumberofTests; t++) {
            String[] values = in.readLine().split("\\s+");
            x[t] = (int) Long.parseLong(values[0]);
            y[t] = (int) Long.parseLong(values[1]);
        }
        //int N = (MaxN > MODULO) ? MODULO :  MaxN;
        //int K = (MaxK > MODULO) ? MODULO : MaxK;

        for (int t = 0; t < iNumberofTests; t++) {
            if (y[t] > (x[t] + 1) / 2)
                System.out.println(0);
            else {
                int result = createMatrix((int) (y[t] % MODULO + 1), (int) (x[t] % MODULO + 1));
                System.out.println(result);
            }
        }
        in.close();
    }

    private int createMatrix(int k, int n) {
        int[] temp = new int[n];
        for (int i = 0; i<n; i++){
            temp[i] = i;
        }

        for (int i = 2; i < k; i++) {
            int[] temp2 = new int[n];
            for (int j = i; j < n; j++) {
                int x = (temp2[j-1] + temp[j-2]) % MODULO;
                temp2[j] = x;
            }
            temp = temp2;
        }
        return temp[n - 1];
    }

    public static void main(String[] args) throws IOException {
        Locale.setDefault(Locale.US);
        new Solution().run();
    }
}