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

typedef long long ll;

const ll mod = 100003;
ll count(ll x) {
    return (x/mod) + (x/(mod*mod));
}

ll power(ll A, ll b) {
    A %= mod;
    if (b == 0) return 1ll;
    if (b % 2ll == 0ll) return power( (A*A) % mod, b/2ll);
    return (A*power(A, b-1ll)) % mod;
}

ll fact(ll n) {
    ll x = n / mod;
    ll y = n % mod;
    ll ans = 1;
    for (ll i = 1; i < mod; ++i)
        ans = (ans * power(i, x)) % mod;
    for (ll i = 1; i <= y; ++i)
        ans = (ans * i) % mod;
    if (x) ans = (ans*fact(x)) % mod;
    return ans;
}

ll comb(ll A, ll B) {
    if (A < B) return 0;
    if (count(A) != count(B) + count(A-B)) return 0;
    ll up = fact(A);
    ll down = (fact(B) * fact(A-B)) % mod;
    return (up*power(down, mod-2)) % mod;
}

int main() {
    ll T;
    cin >> T;
    while (T--) {
        ll N, K;
        cin >> N >> K;
        cout << comb(N-K+1ll, K) << "\n";
    }
    return 0;
}