//tonynater - HackerRank 2014 #include <cassert> #include <iostream> using namespace std; #define sz(x) ((int) x.size()) typedef long long ll; const ll MOD = 100003; int T; ll P[MOD], N, K; ll bp(ll bs, ll ex) { if(ex == 0) { return 1; }else { ll h = bp(bs, ex/2); ll f = (h*h)%MOD; if(ex%2 == 0) { return f; }else { return (f*bs)%MOD; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); P[0] = 1; for(ll i = 1; i < MOD; i++) { P[i] = (P[i-1]*i)%MOD; } cin >> T; for(int t = 0; t < T; t++) { cin >> N >> K; ll a = N-K+1; ll b = K; if(a < b) { cout << "0\n"; continue; } ll p1 = a/MOD+a/MOD/MOD; ll f1 = bp(P[MOD-1], a/MOD); f1 *= P[a%MOD]; f1 %= MOD; f1 *= bp(P[MOD-1], a/MOD/MOD); f1 %= MOD; f1 *= P[(a/MOD)%MOD]; f1 %= MOD; f1 *= P[(a/MOD/MOD)%MOD]; ll p2 = b/MOD+b/MOD/MOD; ll f2 = bp(P[MOD-1], b/MOD); f2 *= P[b%MOD]; f2 %= MOD; f2 *= bp(P[MOD-1], b/MOD/MOD); f2 %= MOD; f2 *= P[(b/MOD)%MOD]; f2 %= MOD; f2 *= P[(b/MOD/MOD)%MOD]; ll p3 = (a-b)/MOD+(a-b)/MOD/MOD; ll f3 = bp(P[MOD-1], (a-b)/MOD); f3 *= P[(a-b)%MOD]; f3 %= MOD; f3 *= bp(P[MOD-1], (a-b)/MOD/MOD); f3 %= MOD; f3 *= P[((a-b)/MOD)%MOD]; f3 %= MOD; f3 *= P[((a-b)/MOD/MOD)%MOD]; if(p1 > p2+p3) { cout << "0\n"; }else { ll res = f1; res *= bp(f2, MOD-2); res %= MOD; res *= bp(f3, MOD-2); res %= MOD; cout << res << '\n'; } } return 0; }