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

题目描述

这是问题的困难版本。两个版本的区别在于对 $m$ 的限制，在这个版本中， $2≤m≤10^{15}$且每个测试点都是独立的。

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

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

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

输入格式

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

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

每个测试用例都是独立的。

输出格式

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

样例

6
3 3
3 2
2 2948
2 8261
7 830980000000
6 535700000000

5
3
171820493
566853963
471470948
607589737

样例解释

对于第一组样例：

方案 1：不放骨牌。

方案 2：放左上角。

方案 3：只放右上角。

方案 4：只放左下角。

方案 5：只放右下角。

一共5种。