#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod=1e5+3; 
int dp[601][100005];
int main() {
    int a;cin>>a;
    for (int g=0;g<a; g++)
    {
        int b,c;cin>>b>>c;
        if (b>100000 || c>600)
            {
        for (int g=1;g<=b+2; g++)
        dp[0][g]=1; 
        for (int g=1;g<=c; g++) // the number of girlfriends
            {
            for (int y=b;y>=1; y--)// the position
                {
                dp[g][y]=dp[g][y+1]+dp[g-1][y+2]; dp[g][y]%=mod; 
            }
        }cout << dp[c][1] << '\n';continue; 
        }
        for (int g=0;g<=c; g++) dp[g][0]=0;
        for (int g=0;g<=b; g++) {dp[0][g]=1; }
        for (int g=1;g<=c; g++) // the number of girlfriends
            {
            for (int y=1;y<=b; y++)// the position
                {
                if (y-2<=0)
                    {
                    dp[g][y]=dp[g][y-1]+dp[g-1][0]; 
                }
                else
                dp[g][y]=dp[g][y-1]+dp[g-1][y-2]; dp[g][y]%=mod; 
            }
        }cout << dp[c][b]<<'\n';
    }
    return 0;
}