题目描述

小$s$正在玩一个游戏 : 他有一个长为$N$, 宽为$M$的棋盘, 其中有一些格子是黑色的.(其余的格子是白色的)

每次操作他可以选择一个长度和宽度均大于$1$的矩形区域, 如果其中3个角落的格子是黑色的, 那么他可以把剩余那个角落的白色格子涂成黑色.

试求出有多少种不同的长为$N$, 宽为$M$的棋盘, 满足小$s$可以通过有限次操作把整个棋盘变成黑色，并且黑色格子个数最少. 两个棋盘不同当且仅当存在一个格子在两个棋盘中的颜色不同.

你只需要输出这个数字对$998244353$取模后的结果.

输入格式

第一行一个正整数$T$, 表示数据组数. 对于每组测试数据, 第一行输入两个正整数$N$和$M$.

数据范围 : 对于所有数据, 满足$1 \leq T \leq 100$, $1 \leq N \leq 100$, $1 \leq M \leq 100$.

输出格式

对于每组数据, 输出一行一个整数表示答案.

样例输入

2
1 1
2 2

样例输出

1
4