A6760 | $「THUPC 2018」生生不息 / Lives$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

生命游戏是一个经典的零玩家游戏。 游戏在一块 $n \times m$ 的方格棋盘上进行，初始时，棋盘上的一些格子中有生命，另一些格子中没有生命。 在新的一天开始时，如果一个格子周围的 $8$ 个（边界上的格子也许不到 $8$ 个）格子中，在前一天有恰好$2$个或$3$个格子中有生命，则这个格子上的生命可以继续生存，如果周围的格子中有$3$个格子在前一天有生命且这个格子中前一天没有生命，则会在这个格子中诞生新的生命。在其他情况下，该格子中原有的生命则会死去且不会产生新的生命。 如果在某一天，棋盘上所有的格子里都没有生命，显然，在接下来的时间里，所有的格子中再也不会有生命了，我们就说这些生命灭绝了。 现在，牛牛希望让菲菲来决定游戏开始时棋盘上的每个格子中是否有生命。 而他想知道，在游戏开始时，菲菲有多少种不同的方法使得棋盘上的生命永远也不会灭绝。

输入包含多组数据，第一行一个整数 $T$ 表示数据组数。（$T <= 30$） 接下来依次描述每组数据，对于每组数据： * 一行 $2$ 个正整数 $n$、$m$。（$n、m<=5$）

对于每组数据，输出 $1$ 行： * 一行输出 $1$ 个整数，表示问题的答案。

输入 #1

2
2 2
3 3

输出 #1

5
150

C++ 编辑器

输入

输出