# https://yukicoder.me/problems/no/2529 MOD = 998244353 class CombinationCalculator: """ modを考慮したPermutation, Combinationを計算するためのクラス """ def __init__(self, size, mod): self.mod = mod self.factorial = [0] * (size + 1) self.factorial[0] = 1 for i in range(1, size + 1): self.factorial[i] = (i * self.factorial[i - 1]) % self.mod self.inv_factorial = [0] * (size + 1) self.inv_factorial[size] = pow(self.factorial[size], self.mod - 2, self.mod) for i in reversed(range(size)): self.inv_factorial[i] = ((i + 1) * self.inv_factorial[i + 1]) % self.mod def calc_combination(self, n, r): if n < 0 or n < r or r < 0: return 0 if r == 0 or n == r: return 1 ans = self.inv_factorial[n - r] * self.inv_factorial[r] ans %= self.mod ans *= self.factorial[n] ans %= self.mod return ans def calc_permutation(self, n, r): if n < 0 or n < r: return 0 ans = self.inv_factorial[n - r] ans *= self.factorial[n] ans %= self.mod return ans def solve(N, M): matrix =[[0] *3 for _ in range(3)] # 向き先が0 for i in range(3): matrix[i][0] = 1 # 向き先が1 for i in range(3): matrix[i][1] = N - i # 向き先が2 if N <= 3: matrix[0][2] = 0 else: y = (N * (N - 3)) % MOD matrix[0][2] = (y * pow(2, MOD - 2, MOD)) % MOD matrix[1][2] = ((N - 3) * (N - 2)) % MOD matrix[1][2] *= pow(2, MOD - 2, MOD) matrix[1][2] %= MOD if N <= 3: matrix[2][2] = 0 else: y1 = pow(N - 2, 2, MOD) y1 -= (N - 2) y1 %= MOD y1 *= pow(2, MOD - 2, MOD) y1 %= MOD y1 -= N - 4 y1 %= MOD matrix[2][2] = y1 dp = [0] * 3 dp[0] = 1 for _ in range(M): new_dp = [0] * 3 for j in range(3): for k in range(3): new_dp[k] += (dp[j] * matrix[j][k]) % MOD new_dp[k] %= MOD dp = new_dp answer = 0 for j in range(3): answer += dp[j] answer %= MOD return answer def main(): T = int(input()) answers = [] for _ in range(T): N, M = map(int, input().split()) ans = solve(N, M) answers.append(ans) for ans in answers: print(ans) if __name__ == "__main__": main()