#include <bits/stdc++.h>
//#include "testlib.h"
using namespace std ;
#define LL long long int
#define ft first
#define sd second
#define PII pair<int,int>
#define MAXN 200005
#define MAXM 1001
#define mp make_pair
#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)
//#define sc(x) scanf("%d",&x)
//#define scll(x) scanf("%lld",&x)
#define sc(x) cin >> x
#define scll(x) cin >> x
#define pr(x) cout << x << "\n"
#define prll(x) cout << x << "\n"
//#define pr(x) printf("%d\n",x)
//#define prll(x) printf("%lld\n",x)
#define all(x) x.begin(),x.end()
#define pb push_back
#define MOD 1000000000
#define ASST(x,l,r) assert(x >= l && x <= r)
 
int n , m , nCr[4444][4444] , dp2[2222][2222];
 
void pre(){
    for(int i=0;i<=4000;i++)
        nCr[i][0] = 1 ;
    for(int i=1;i<=4000;i++)
        for(int j=1;j<=i;j++)
            nCr[i][j] = ( nCr[i-1][j-1] + nCr[i-1][j] ) % MOD ;
}
void solve(){
    sc(n) ; sc(m) ;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
            dp2[i][j] = 0 ;
 
    dp2[0][0] = 1 ;
    for(int i=1;i<=n;i++){
        int s = 0 ;
        for(int j=0;j<=m;j++){
            s += dp2[i-1][j] ;
            if(s >= MOD) s -= MOD ;
            dp2[i][j] = 1LL * s * nCr[j+m-1][m-1] % MOD ;
        }
    }
    int ans = 0 ;
    for(int i=0;i<=m;i++){
        ans += dp2[n][i] ;
        if(ans >= MOD) ans -= MOD ;
    }
    pr(ans) ;
}
 
 
int main(){
    int t ;
    pre() ;
    sc(t) ;
    while(t --){
        solve() ;
    }
    return 0 ;
}