Problem Description

给定 $c$，设 $q_k$ 表示有一个 $2\times k$ 的矩阵，初始时所有位置均为空，要从中选出 $k$ 个位置涂上 $0,1,\dots,c$ 的数字，使得每列至多存在一个数字非 $0$ 的方案数。

每个位置只能涂上一种数字。

空的位置与染上任何一个数字的位置都是不同的。

每种数字可以出现在多个位置上。

给定 $n$，求 $q_1,q_2,\dots,q_n$ 模 $998244353$。

为了减小输出量，只需要输出它们的异或和即可。

Input

本题有多组测试数据。

第一行，一个正整数 $T$ $(1 \le T \le 5)$ 表示数据组数。

对于每组数据，第一行两个整数 $n,c$ $(1 \le n \le 10^7,0 \le c < 998244353)$。

Output

对于每组数据，一行一个非负整数，表示 $q_1,q_2,\dots,q_n$ 模 $998244353$ 后的异或和。

3
5 0
3 1
3 2

170
154
420

Hint

对于第一组数据：
异或前的结果为 [2, 6, 20, 70, 252]。
对 q[1]，考虑将第 1 行第 1 列的格子或第 2 行第 1 列的格子涂上 0 即可。
对 q[2]，考虑任意选出两个格子涂上 0 即可。

对于第二组数据：
异或前的结果为 [4, 22, 136]。
对 q[1]，考虑将第 1 行第 1 列的格子或第 2 行第 1 列的格子涂上 0 或 1 即可。

对于第三组数据：
异或前的结果为 [6, 46, 396]。