#include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<map>

 #include<cmath>

 #include<stdlib.h>

 using namespace std;

 #define LL long long

 #define mod 10000003

 int cc[][];

 void cn(int n,int m)

 {

     int i,j;

     for(i =  ; i <= n ;i++)

     {

         cc[i][] = ;

         cc[i][i] = ;

         cc[i][] = i;

     }

     for(i = ; i <= n ; i++)

         for(j = ; j <= m ; j++)

         cc[i][j] = (cc[i-][j]%mod+cc[i-][j-]%mod)%mod;

 }

 int main()

 {

     int c,n,k,i;

     cn(,);

     cin>>c;

     while(c--)

     {

         cin>>n>>k;

         printf("%d\n",cc[n][k]);

     }

     return ;

 }

 /**************************************

     Problem id    : SDUT OJ 2164

     User name    : shang

     Result        : Accepted

     Take Memory    : 4420K

     Take Time    : 10MS

     Submit Time    : 2014-01-18 16:32:30

 **************************************/