import java.io.*;
import java.util.*;
import java.math.*;

public class Solution {
		
	static int[] pri = new int[10000];
	static boolean[] vis = new boolean[100005];
	static int prc;
	
		public static void main(String[] args) throws IOException{
			// TODO Auto-generated method stub
			Scanner sc = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
			int i,j,c,res,rep,m2;
			long n,k,nbound,ans,a,b;
//			double t;
			long[] mk = new long[5]; long[] nk = new long[5];
			BigInteger ma = new BigInteger(String.valueOf(100003));
			
			
			Arrays.fill(vis,true);
			vis[1] = false;
			for(i=2;i<=10004/2;i++)
				if (vis[i]) {
					
					j = 2*i;
					while (j<=100004) {
						vis[j] = false;
						j += i;
					}
				}
			
			prc = 0;
			Arrays.fill(pri,0);
			for(i=2;i<=100004;i++)
				if (vis[i]) {
					prc++;
					pri[prc] = i;
				}
			
//	 a = 999999; System.out.println((a*(a-1)/2) % 100003);		
			
		res = sc.nextInt();
		m2 = 100003;
		nbound = 10000000;
		for(rep=0;rep<res;rep++){
			
			n = sc.nextLong();
			k = sc.nextLong();
//			System.out.println(n);
			if (2*k-1>n) {
				System.out.println(0);
				continue;
			}
			
	/*		if ((n>=nbound)&&(k<=n/4)) {
				System.out.println(0);
				continue;
			}*/
			n = n-k+1;
			
			c=0;
			while (k!=0){
				nk[c] = k % m2;
				k /= m2;
				c++;
			}
//			for(i=0;i<=c;i++) System.out.println(nk[i]);
			c=0;
			while (n!=0){
				mk[c] = n % m2;
				n /= m2;
				c++;
			}
			c--;
	//		for(i=0;i<=c;i++) System.out.println(mk[i]+" "+nk[i]+" "+c);
			
			ans = 1;
			for(i=0;i<=c;i++) {
				
				ans *= binmodp(mk[i],nk[i],100003);
//				System.out.println(ans+" "+i);
				ans %= 100003;
				
			}
			System.out.println(ans);
//			System.out.println(n2.toString());
			
		}
	}
		
		public static long binmodp(long n, long k, long p) {
			
			int[] pow = new int[10000];
			int i,c; long j;
			long ans;
			
			if (n<k) return 0;
			if ((n==k)||(k==0)) return 1;
			
			Arrays.fill(pow,0);
			i = 1;
			while ((pri[i]!=0)&&(pri[i]<=n)) {
				j = pri[i];
				c = 0;
				while (j<=n) {
					c += n/j;
					j *= pri[i];
				}
				pow[i] = c;
				i++;
			}
			
			i = 1;
			while((pri[i]!=0)&&(pri[i]<=k)) {
				j = pri[i];
				c = 0;
				while (j<=k) {
					c += k/j;
					j *= pri[i];
				}
				pow[i] -= c;
				i++;
			}
			
			i = 1;
			while ((pri[i]!=0)&&(pri[i]<=n-k)) {
				j = pri[i];
				c = 0;
				while (j<=n-k) {
					c += (n-k)/j;
					j *= pri[i];
				}
				pow[i] -= c;
				i++;
			}
			
			i = 1; ans = 1;
			while((pri[i]!=0)&&(pri[i]<=n)) {
				ans *= emodp(pri[i],pow[i],p);
				ans %= p;
				i++;
			}
			return ans; //change here soon
		}
		
		public static long emodp(long x, long n, long p) {
			long t;
			x %= p;
			if (n==0) return 1;
			else if (n==1) return x;
			else if (n % 2 == 0) return emodp(x*x,n/2,p);
			else {
				t = x * emodp(x*x,(n-1)/2,p);
				return t % p;
			}
		}
}