分割棋盘

题目描述

求把 $N×M$ 的棋盘分割成若干个 $1×2$ 的长方形，有多少种方案。

例如当 $N=2，M=4$ 时，共有 $5$ 种方案。当 $N=2，M=3$ 时，共有 $3$ 种方案。

如下图所示：

输入格式

首先输入一个正整数 $T$，代表测试数据的多少。

接下来的 $T$ 行每组测试用例占一行，包含两个整数 $N$ 和 $M$。

输出格式

每个测试用例输出一个结果，每个结果占一行。

样例 #1

样例输入 #1

5
1 2
1 3
1 4
2 2
2 3

样例输出 #1

1
0
1
2
3

提示

【数据范围】$1≤N,M≤11$