#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
unsigned long long original_N;
unsigned long long original_K;

unsigned int lovers_helper(int N, int K, unsigned int *saved)
{
    if (N == 0 || K == 0) {
        return 0; 
    }
    if (*(saved + (N-1)*original_K + (K-1))) {
        return *(saved + (N-1)*original_K + (K-1));
    }
    else if (K == 1) {
        *(saved + (N-1)*original_K + (K-1)) = N;
        return N;
    }
    else if (N == K) {
        *(saved + (N-1)*original_K + (K-1)) = 0;
        return 0;
    }
    else {
        *(saved + (N-1)*(original_K) + (K-1)) = lovers_helper(N - 2, K -1, saved) + lovers_helper(N - 1, K, saved);
        return *(saved + (N-1)*original_K + (K-1));
    }
}

unsigned int lovers(unsigned int N, unsigned int K)
{
    unsigned int *saved = (unsigned int*) malloc(sizeof(unsigned int)*N*K);
    memset(saved,0,sizeof(unsigned int)*N*K);
    lovers_helper(N,K,saved);
    return *(saved + (N-1)*original_K + (K-1));
}

int main() {
    int t;
    
    cin >> t;
    for (int i = 0; i < t; ++i) {
        cin >> original_N;
        cin >> original_K;
        cout << lovers(original_N,original_K) % 100003 << endl;
    }

    
    
    return 0;
}