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

public class Solution {
    public static int countWays(int houses, final int girlfriends) {   
        int ways = 0, step = 2;
        for( int i = 0; i < houses; i++ ) {
            for(int j = step; j < (houses - i); j++) {
                if(canVisit(houses,girlfriends,j,i))
                    ways++;
            }
        }
        return ways;
    }
    public static boolean canVisit(int houses, int girlfriends, int step, int start) {
        int location = start, visitedGirlfriends = 0;
        while(location < houses) {
            location = location + step;
            visitedGirlfriends++;
        }
        if(visitedGirlfriends >= girlfriends)
            return true;
        else
            return false;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		for(int i = 0; i < n; i++) {
            int houses = in.nextInt(), girlfriends = in.nextInt();
            System.out.println(countWays(houses,girlfriends) % 100003);
		}
    }
}