#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

const LL MOD = 1e4 + ;

LL quick_pow (LL a,LL b,LL MOD) {

    //求解 a^b%MOD的值

    LL base=a%MOD;

    LL ans=; //相乘，所以这里是1

    while (b) {

        if (b&) {

            ans=(ans*base)%MOD; //如果这里是很大的数据，就要用quick_mul

        }

        base=(base*base)%MOD;    //notice

        //注意这里,每次的base是自己base倍

        b>>=;

    }

    return ans;

}

LL C (LL n,LL m,LL MOD) {

    if (n<m) return ; //防止sb地在循环，在lucas的时候

    if (n==m) return ;

    LL ans1 = ;

    LL ans2 = ;

    LL mx=max(n-m,m); //这个也是必要的。能约就约最大的那个

    LL mi=n-mx;

    for (int i = ; i <= mi; ++i) {

        ans1 = ans1*(mx+i)%MOD;

        ans2 = ans2*i%MOD;

    }

    return (ans1*quick_pow(ans2,MOD-,MOD)%MOD); //这里放到最后进行,不然会很慢

}

LL Lucas (LL n,LL m,LL MOD) {

    LL ans=;

    while (n && m && ans) {

        ans=ans*C(n%MOD,m%MOD,MOD)%MOD;

        n /= MOD;

        m /= MOD;

    }

    return ans;

}

LL calc(LL x, LL y) {

    LL ans = (Lucas( * x, x, MOD) + MOD - Lucas( * x, x + , MOD)) % MOD;

    return ans;

}

void work() {

    LL x, y;

    cin >> x >> y;

    if (y == ) {

        cout <<  << endl;

    } else {

        if (x == y) {

            cout << calc(x, y) << endl;

        } else {

            cout << (Lucas(x + y, y, MOD) - Lucas(x + y, y - , MOD) + MOD) % MOD << endl;

        }

    }

}

int main() {

#ifdef local

    freopen("data.txt","r",stdin);

#endif

//    for (x = 1; x <= 10; ++x) {

//        for (y = 0; y <= x; ++y) {

//            work();

//        }

//        cout << endl;

//    }

    IOS;

    int t;

    cin >> t;

    while (t--) work();

    return ;

}