1930: 递推公式计算
内存限制：128 MB
时间限制：5.000 S
评测方式：文本比较
命题人：
提交：103
解决：38
题目描述
已知递推公式如下：
f(m, n) = m n=1时
n m=1时
f(m, n-1) + f(m-1, n) m＞1且n＞1时
请编写算法计算此递推式。
输入
第一行为测试用例个数k，k≤1000。
后面n行，每行为一个测试用例，每个测试用例为两个空格隔开的不小于1的整数m和n，m≤1000，n≤1000。
输出
因为计算结果值可能会非常巨大，所以对每个测试用例，输出f(m, n)模除10000的结果，每个输出占一行。
样例输入 复制
2
2 3
3 5
样例输出 复制
7
41