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

unsigned long long power(unsigned long long base, unsigned long long e)
{
    unsigned long long res = 1;
    while (e)
    {
        if (e%2) res = (res*base)%100003;
        e /= 2;
        base = (base*base)%100003;
    }
    return res;
}

int deg(unsigned long long n)
{
	int D = 0;
	unsigned long long a = 100003;
	while (a <= n) { D += n/a; a *= 100003; }
	return D;
}

// after tons of combinatorics i get
// f(K, N) = (N-K+1) choose (N-2K+1)
// f(K, N) = (N-K+1) choose K

int main() {
	int numTests; cin >> numTests;
	while (numTests > 0)
	{
		unsigned long long N, K; cin >> N >> K;
		if (K == 0) cout << "1" << endl;
        else if (N < 2*K - 1) cout << "0" << endl;
        else
        {
        	int C = (K < N-2*K+1?K:N-2*K+1);
        	if (deg(N-K+1) - deg(N-K+1-C) > deg(C)) cout << "0" << endl;
        	else
        	{
				unsigned long long ans = 1; 
				for (unsigned long long i = N-K+1; i > N-K+1-C; --i)
				{
					int k = i; while (k%100003 == 0) k /= 100003;
					ans *= k%100003; ans %= 100003;
				}

				unsigned long long b = 1;
				for (unsigned long long i = C; i > 0; --i)
				{
					int k = i; while (k%100003 == 0) k /= 100003;
					b *= k%100003; b %= 100003;
				}
				ans *= power(power(b, 11), 9091);
				cout << ans%100003 << endl;
			}
        }
        --numTests;
	}
}