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

题目描述

王老师很轻松就解决了“王老师的多骨诺米牌”这道题，王老师想了想，发现m特别大的时候也可以解决，为了考验大家，于是在上题的基础上只改动了m。

输入格式

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

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

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

输出格式

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

样例

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

471470948
607589737
171820493
566853963
5
3