#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>

using namespace std;

const int MOD = 100003;

int main() {
	/* Enter your code here. Read input from STDIN. Print output to STDOUT */   
	int T;
	long long N, K;
	cin>>T;
	for (int t = 0; t < T; ++t)
	{
		cin>>N>>K;
		std::vector<std::vector<int> > cnt(N + 1, std::vector<int>(K + 1, 0));
		for (long long n = 0; n <= N; ++n)
		{
			for (long long k = 0; k <= K; ++k)
			{
				if (n == 0)
				{
					if (k == 0)
					{
						cnt[n][k] = 1;
					}
					else
					{
						cnt[n][k] = 0;
					}
				}
				else if (k == 0)
				{
					cnt[n][k] = cnt[n - 1][k];
				}
				else if (n == 1)
				{
					if (k == 1)
					{
						cnt[n][k] = 1;	
					}
					else
					{
						cnt[n][k] = 0;
					}
				}
				else
				{
					cnt[n][k] = (cnt[n - 2][k - 1] + cnt[n - 1][k]) % MOD;
				}
			}
		}
		cout<<cnt[N][K]<<endl;

	}	
	return 0;
}