铺放骨牌

题目描述:

用1×2的骨牌覆盖n×m棋盘，问有多少种摆法，如图为n=m=10的棋盘的一种摆法：

输入格式:

每个测试点中含有多组数据。
第一行一个数T，代表一共有T组数据。
接下来一共有T行，每行两个数n和m，用空格隔开。

输出格式:

一共T行，每行一个数，表示最终的答案。

样例输入:

4
2 2
2 3
2 4
2 5

样例输出:

2
3
5
8

提示:

对于20%的数据，nm<=10，T<=10
对于另外20%的数据，n和m中有一个为2，T<=10
对于所有数据，4<=nm<=100，nm为偶数，T<=50。
改编自UVa 11270。
数据为ljc随机生成。

时间限制: 1000ms
空间限制: 256MB

---

来源: by ljc