题目描述

生命游戏是一个经典的零玩家游戏。

游戏在一块 $n \times m$ 的方格棋盘上进行，初始时，棋盘上的一些格子中有生命，另一些格子中没有生命。

在新的一天开始时，如果一个格子周围的 $8$ 个（边界上的格子也许不到 $8$ 个）格子中，在前一天有恰好$2$个或$3$个格子中有生命，则这个格子上的生命可以继续生存，如果周围的格子中恰好有$3$个格子在前一天有生命且这个格子中前一天没有生命，则会在这个格子中诞生新的生命。在其他情况下，该格子中原有的生命则会死去且不会产生新的生命。

如果在某一天，棋盘上所有的格子里都没有生命，显然，在接下来的时间里，所有的格子中再也不会有生命了，我们就说这些生命灭绝了。

现在，牛牛希望让菲菲来决定游戏开始时棋盘上的每个格子中是否有生命。

而他想知道，在游戏开始时，菲菲有多少种不同的方法使得棋盘上的生命永远也不会灭绝。

输入格式

输入包含多组数据，第一行一个整数 $T$ 表示数据组数。（$T <= 30$）

接下来依次描述每组数据，对于每组数据：

• 一行 $2$ 个正整数 $n$、$m$。（$n,m<=5$）

输出格式

对于每组数据，输出 $1$ 行：

• 一行输出 $1$ 个整数，表示问题的答案。

2
2 2
3 3

5
150

提示

来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 Pony.ai 对此次比赛的支持。

题解等资源可在 https://github.com/wangyurzee7/THUPC2018 查看。