【6月2日测试5】数Ⅱ

题号：NC26119
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Rikka 是一个热爱思考的女孩子。

在数学课上，她学习了高中数学课本中的“数列”的概念。

在算法竞赛中，“数列”可以近似地看作是“数组”，我们定义数列 $\{a_n\}$ 的第 i 项为 $a_i$ ，定义一个所有项都一样的数列为常数数列。

老师告诉她，如果定义一个新数列 $\{d_n\}$ 使 $d_i = a_{i + 1} - a_{i}$ ，那么数列 $\{d_n\}$ 被称为数列 ${a_n}$ 的差分数列，构造数列 $\{d_n\}$ 的过程被称为差分。

容易发现，一个长度为 n 的数列 $\{a_n\}$ 在一次差分之后会得到一个长度为 n - 1 的差分数列。

现在 Rikka 有一个特殊的无穷多项的数列 $\{a_n\}$ ，其中 $a_i = c \times i ^ k$ ，c 和 k 是两个给定的常数。举一个最简单的例子，当 c = 1，k = 2 时，这个数列可以表示成 $\{1, 4, 9, 16, 25, \cdots\}$ 。

Rikka 惊奇地发现，把这个数列差分 k 次后会得到一个常数数列，现在她想知道，这个常数数列中的数是多少。

请你来帮助 Rikka 回答这个问题。

输入描述:

输入包括 T + 1 行。

第一行是一个整数 T，表示 Rikka 的询问次数。

接下来有 T 行，每行两个整数 c 和 k，表示这一次询问中数列的两个常数。

输出描述:

输出包括 T 行。

对于每一个询问，输出一行一个整数，表示这一个询问的答案。

你也知道 Rikka 的数学不好，所以只需要告诉她这个答案对 998244353 取模后的值。

示例1

输入

复制

3
9 3
11 2
12345678 12345678

输出

复制

54
22
457610225

说明

### 样例解释

对于第一组测试数据，生成的数列为 。

一次差分后变成 。

第二次差分后变成 。

第三次差分后变成 。

最后答案就是 54。

第二、三组类似。

备注:

保证对于所有的测试数据，，，。