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();
    }
  }

}