#include <cstdio> #include <algorithm> using namespace std; const int MOD = 100003; long long N, K; int T; long long fac[MOD]; inline pair<long long, long long> calc(long long n) {//mod, pow if (n < MOD) { return make_pair(fac[n], 0LL); } int rem = n % MOD; long long p = n / MOD; pair<long long, long long> ret = calc(p); ret.second += p; ret.first = (ret.first * fac[rem]) % MOD; if (p & 1) { ret.first = (MOD - ret.first) % MOD; } return ret; } inline long long mypwr(long long bs, int pw) { if (pw == 0) {return 1;} else if (pw == 1) {return (bs % MOD);} else { long long ret = mypwr(bs, pw >> 1); ret = (ret * ret) % MOD; if (pw & 1) { ret = (ret * bs) % MOD; } return ret; } } int main() { fac[0] = 1; for(int i = 1 ; i < MOD ; i++) { fac[i] = (fac[i - 1] * i) % MOD; } scanf("%d", &T); for(int t = 1 ; t <= T ; t++) { scanf("%lld %lld", &N, &K); N = N - K + 1; if (N < K) { printf("0\n"); } else if (N == K) { printf("1\n"); } else { pair<long long, long long> A = calc(N); pair<long long, long long> B = calc(K); pair<long long, long long> C = calc(N - K); if (A.second > B.second + C.second) { printf("0\n"); } else { long long ans = (A.first * mypwr(B.first, MOD - 2)) % MOD; ans = (ans * mypwr(C.first, MOD - 2)) % MOD; printf("%lld\n", ans); } } } return 0; }