荷兰画家皮特·蒙德（Piet Mondrian）对矩形填充情有独钟。在一场梦中，他想用若干块 的小矩形（可以水平或竖直摆放）完全覆盖一块 的大矩形。 下面给出一组示例（黑色区域为一块 小矩形，图省略）： 的大矩形的 种可能的合法填充。 现在请你帮助蒙德计算：给定 ，不同填充方案的数量。若无法完全覆盖，则答案为 。 需要注意的是，大矩形定向，即若两种方案通过翻转 旋转得到但铺砌形状不同，也视为不同方案。

输入描述:

第一行输入整数 ——测试用例数量。 接下来 行，每行两个整数 ，表示大矩形的行数与列数。

输出描述:

对于每个测试用例，输出一个整数，表示使用 小矩形完全覆盖 大矩形的方案数。若无法覆盖，输出 。