1364 : 赤驴

时间限制:1 Sec 内存限制:128 MiB
提交:176 答案正确:81

提交 状态 讨论区

题目描述

赤驴是一匹马,小名叫小驴。是的,你没有看错、这个名字里面有个驴字的东西真的是匹马、而且是一匹已经练就火眼金睛、并且上知天文下知地理的极度不科学的马。那为什么它的名字里面会有个驴字呢?见鬼、我怎么知道、问上帝去吧。。。好啦,撇开这个不说了。现在这小驴的头被门挤了一下、然后重重的晕了过去、然后就做了这个怪梦。
    小驴梦到自己来到了一个陌生的世界,这个世界是一个m*n的矩阵(坐标编号从0开始),并且发现自己在左上角(0,0)点、同时、它用它的火眼金睛瞅了瞅、发现这个世界有且只有一个唯一的出口,在右下角(m-1,n-1)的位置。好了、现在小驴要去出口了,可能它象棋玩多了吧、在这个梦里面、它是蹦跶着走的、并且的蹦的方式和中国象棋中的马一模一样。
    这头不科学的马觉得直接走出这个世界不好玩、于是想计算一下自己有多少种蹦跶的方式可以离开这个世界。

注意:
    由于未知原因(可能是头被门挤坏了吧。。),小驴每次都只会朝右下方向跳跃。

输入

输入数据有多组。首先输入一个整数ncase,表示输入的组数。然后是ncase组输入,每组输入占一行,由两个整数组成,分别是m、n(2<=n,m<=40)。

输出

每组数据输出一个整数、占一行,表示从(0,0)到(m-1,n-1)有多少种不同的路线。

样例输入

复制
3
2 2
2 3
4 4

样例输出

复制
0
1
2

提示


			

来源