该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

王老师喜欢玩多骨诺米牌，现在他想要在 $n×m(n≤8)$ 的网格上放置若干个$2\times2$的骨牌，不允许重叠，不要求铺满 ，求方案数。

两种方案不同当且仅当，存在一个格子在一种方案中是空的而在另一种方案中被铺上了骨牌。

由于答案可能很大，你只需要输出答案对 $998244353$ 取模后的值。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量$t(1≤t≤1000)$。

每个测试用例的第一行都包含两个整数，$n,m(n≤8,2≤m≤10^5)$。

每个测试，m的总和不超过$1\times 10^5$。

输出格式

对于每个测试用例，输出一行一个整数表示答案，答案对 $998244353$ 取模。

样例

6
7 83098
6 5357
2 2948
2 8261
3 3
3 2

661826802
567565941
171820493
566853963
5
3

样例解释

对于第五组样例：

方案 1：不放骨牌。

方案 2：放左上角。

方案 3：只放右上角。

方案 4：只放左下角。

方案 5：只放右下角。

一共5种。