import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    final static int mod = 100003;
    static long[] factorial = new long[mod + 1];
    static long[] inverse = new long[mod + 1];

    public static void main(String[] args) {
        Scanner keyboard = new Scanner(System.in);

        long factor = 1, v = 1;
        factorial[0] = inverse[0] = 1;
        for (int i = 1; i <= mod; i++) {
            factor = (factor * i) % mod;
            factorial[i] = factor;
            v = (v * modInverse(i)) % mod;
            inverse[i] = v;
        }

        int t = keyboard.nextInt();
        while(t-- > 0) {
            BigInteger n = keyboard.nextBigInteger();
            BigInteger k = keyboard.nextBigInteger();
            n = n.subtract(k).add(BigInteger.ONE);
            long r = 1;
            while(n.compareTo(BigInteger.ZERO) > 0 && k.compareTo(BigInteger.ZERO) > 0) {
                int n1 = n.mod(BigInteger.valueOf(mod)).intValue();
                int k1 = k.mod(BigInteger.valueOf(mod)).intValue();
                
                if(k1 > n1) {
                    r = 0;
                    break;
                }

                r = r * factorial[n1] % mod;
                r = r * inverse[k1] % mod;
                r = r * inverse[n1-k1] % mod;

                n = n.divide(BigInteger.valueOf(mod));
                k = k.divide(BigInteger.valueOf(mod));
            }
            System.out.println(r);
        }
    }

    static long modInverse(long i) {
        long pow = mod - 2;
        long ret = 1;
        while (pow > 0) {
            if ((pow & 1) > 0)
                ret = ret * i % mod;
            i = i * i % mod;
            pow >>= 1;
        }
        return ret;
    }
}