#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


  /* Enter your code here. Read input from STDIN. Print output to STDOUT */
int main(){
    int num_test;
    cin>>num_test;
    for(int i=0; i<num_test; i++){
        unsigned long long N;
        unsigned long long K;
        cin>> N;
        cin>> K;
        vector<vector<unsigned long long> > F(N+1,vector<unsigned long long>(K+1));
        //base case:
        for(unsigned long long  j=1; j<=K; j++){
            F[0][j] = 0;
        }
        for(unsigned long long  i=0; i<=N; i++){
            F[i][0] = 1;
        }
        F[1][1] = 1;
        for(unsigned long long  i=2; i<=N; i++){
            for(unsigned long long j=1; j<=K; j++){
                F[i][j] = (F[i-1][j] + F[i-2][j-1])%100003;
            }
        }
        cout<<F[N][K]<<endl;
    }
    return 0;

}