最近，无聊的过河船同学发现了一种无聊的迷宫生成算法。
算法过程如下： 一个N * M的矩形区域可以看作N * M个单位网格组成。在每个网格中，随机生成一个从右上角到左下角的L型障碍或者从左上角到右下角的R型障碍（障碍可以被看作一条线段）。

图1：两种障碍
这样便可以生成一个大小为N * M的迷宫，如图2所示。

图2：无聊的迷宫
然后过河船同学想知道，是否存在迷宫内的从迷宫上边界到达迷宫的下边界的路径。这当然不容易，但是在胀鱼同学的帮助下，过河船同学很快解决了这个问题。
然而无聊的过河船同学还是忍不住用眼睛去找从迷宫的上边界到达下边界的路径，可是他经常无论怎么找也找不到，即使尝试了所有可能的路径。于是无聊的过河船同学想知道，随机生成（每个位置的障碍是L型和R型的概率都是0.5）一个大小为N * M的迷宫，存在一条从迷宫上边界到达下边界的路径的概率有多大。
请注意，路径只能从迷宫内部穿过，除起点和终点外不得离开迷宫区域。

第一行是一个正整数T(≤ 36)，表示测试数据的组数，
每组测试数据只有一行，包含两个整数N(1 ≤ N ≤ 3)和M(1 ≤ M ≤ 12)，表示迷宫的行数和列数。

对于每组测试数据，如果概率是p，输出一个整数，表示p * 2NM的值

9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

0
2
6
0
2
24
0
2
78

	对于第二组样例，存在一条从迷宫上边界到达下边界的路径的迷宫有以下两种，概率是2/(22) = 1/2，答案是 1/2 * (22) = 2。
	
	第一种迷宫
	
	第二种迷宫