#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
//#define unsigned long long ulong;

int num_ways(int N, int K) {
    if (N+1<2*K) return 0;
    vector<vector<int> > memo(K, vector<int>(N));
    vector<vector<int> > memo2(K, vector<int>(N));
    for (int i=0; i<N; i++) {
        memo[0][i] = 1;
        memo2[0][i] = i+1;
    }
    for (int i=1; i<K; i++) {
        memo[i][0] = 0;
        memo2[i][0] = 0;
    }
    
    for (int i=1; i<K; i++) {
        unsigned long long sum = 0;
        for (int j=1; j<N; j++) {
            if (j==1) memo[i][j] = 0;
            else memo[i][j] = memo2[i-1][j-2];
            sum += memo[i][j];
            memo2[i][j] = sum % 100003;
        }
    }
    return memo2[K-1][N-1] % 100003;
}



int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */  
    int T; cin >> T;
    for (int i=0; i<T; i++) {
        int N, K; cin >> N; cin >> K;
        cout << num_ways(N, K) << endl;
    }
    
    return 0;
}