import java.io.DataInputStream; import java.io.FileInputStream; import java.io.IOException; import java.io.PrintWriter; import java.util.Arrays; public class Solution { private static Reader in; private static PrintWriter out; public static int mod = 100003; public static long mod_exp(long b, long e) { long r = 1; while (e > 0) { if ((e & 1) == 1) r = (r * b) % mod; b = (b * b) % mod; e >>= 1; } return r; } public static long[] fact, invfact; public static void main(String[] args) throws IOException { in = new Reader(); out = new PrintWriter(System.out, true); fact = new long[mod]; invfact = new long[mod]; fact[0] = 1; invfact[0] = 1; for (int i = 1; i < mod; i++) { fact[i] = (i * fact[i - 1]) % mod; invfact[i] = mod_exp(fact[i], mod - 2); } int T = in.nextInt(); while(T-- > 0) { long N = in.nextLong(), K = in.nextLong(); N = N - K + 1; out.println(binom(N, K)); } out.close(); System.exit(0); } public static long binom(long N, long K) { if (N < K) return 0; long np = N % mod, kp = K % mod; if (kp > np) return 0; long res = fact[(int)np] * invfact[(int)kp] % mod * invfact[(int)(np - kp)] % mod; if (N > mod) res = res * binom(N / mod, K / mod) % mod; return res; } static class Reader { final private int BUFFER_SIZE = 1 << 16; private DataInputStream din; private byte[] buffer; private int bufferPointer, bytesRead; public Reader() { din = new DataInputStream(System.in); buffer = new byte[BUFFER_SIZE]; bufferPointer = bytesRead = 0; } public Reader(String file_name) throws IOException { din = new DataInputStream(new FileInputStream(file_name)); buffer = new byte[BUFFER_SIZE]; bufferPointer = bytesRead = 0; } public String readLine() throws IOException { byte[] buf = new byte[1024]; int cnt = 0, c; while ((c = read()) != -1) { if (c == '\n') break; buf[cnt++] = (byte) c; } return new String(buf, 0, cnt); } public int nextInt() throws IOException { int ret = 0; byte c = read(); while (c <= ' ') c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9'); if (neg) return -ret; return ret; } public long nextLong() throws IOException { long ret = 0; byte c = read(); while (c <= ' ') c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9'); if (neg) return -ret; return ret; } public double nextDouble() throws IOException { double ret = 0, div = 1; byte c = read(); while (c <= ' ') c = read(); boolean neg = (c == '-'); if (neg) c = read(); do { ret = ret * 10 + c - '0'; } while ((c = read()) >= '0' && c <= '9'); if (c == '.') while ((c = read()) >= '0' && c <= '9') ret += (c - '0') / (div *= 10); if (neg) return -ret; return ret; } private void fillBuffer() throws IOException { bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); if (bytesRead == -1) buffer[0] = -1; } private byte read() throws IOException { if (bufferPointer == bytesRead) fillBuffer(); return buffer[bufferPointer++]; } public void close() throws IOException { if (din == null) return; din.close(); } } }