//
//  main.cpp
//  HackerRank - The Lovers
//
//  Created by chelakara prakash on 10/4/14.
//  Copyright (c) 2014 chelakara prakash. All rights reserved.
//

#include <iostream>
#include <unordered_map>
#include <map>

using namespace std;

map<pair<long long, long long>, long long> DP;
map<pair<long long, long long>, bool> Visited;

long long numWays(long long numHouses, long long numToVisit)
{
    if (numToVisit == 0 || numHouses == 0)
        return 0;
    if (numToVisit == 1)
        return numHouses;
    if (numToVisit > numHouses)
        return 0;
    if (Visited[make_pair(numHouses, numToVisit)])
    {
        return DP[make_pair(numHouses, numToVisit)]%100003;
    }
    DP[make_pair(numHouses, numToVisit)] = (numWays(numHouses - 2, numToVisit - 1)%100003 + numWays(numHouses - 1, numToVisit)%100003)%100003;
    Visited[make_pair(numHouses, numToVisit)] = true;
    return DP[make_pair(numHouses, numToVisit)];
}


int main(int argc, const char * argv[])
{
    int numTestCases;
    cin >> numTestCases;
    
    for (int testCase = 0; testCase < numTestCases; testCase++)
    {
        int numHouses, numToVisit;
        cin >> numHouses >> numToVisit;
        cout << numWays(numHouses, numToVisit) << '\n';
    }
    return 0;
}