#6398. 「THUPC2018」生生不息 / Lives

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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

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

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

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

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

输入格式

输入包含多组数据,第一行一个整数 T 表示数据组数。( T <= 30

接下来依次描述每组数据,对于每组数据:

  • 一行 2 个正整数 n m 。( n、m<=5

输出格式

对于每组数据,输出 1 行:

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

样例

样例 1 输入

3
2 2
3 3

样例 1 输出

5
150
150

数据范围与提示

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

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