#P1883. [Ipsc2007]Delicious Cake
[Ipsc2007]Delicious Cake
题目描述
Lenka 烤了一块长方形蛋糕。把蛋糕看成由 个单位方格组成的网格,只允许沿方格边界切割。没有被切开的公共边会把两个相邻方格连在一起,最终蛋糕分成若干个四连通的块。
如果两种切法得到的所有块在原蛋糕上的形状和位置都相同,则视为同一种切法。换句话说,同一个连通块内部不需要保留切痕。
求不同切法的数量。完全不切也算一种切法。


输入格式
第一行一个正整数 ,表示数据组数。接下来每组包含两个正整数 ,分别表示蛋糕的两个边长。原赛输入在每组数据之前有一个空行。
输出格式
每组输出一行一个正整数,表示不同切法的精确数量。
样例
2
1 2
2 2
2
12
数据范围
附带解题报告给出的两边上限分别为 和 。旋转蛋糕不改变切法数量,输入的两边可以交换,因此可写为 ,。