题目描述

给定正整数 $n,k$。

考虑一个序列 $\{a_i\}$，最初 $a = [1,2,3,\ldots,n]$。每过一秒，这个序列里的每个元素都会分裂成它的所有正约数。

例如，当 $n=5$ 时，最初序列是 $[1,2,3,4,5]$，一秒后序列会变成 $[1,1,2,1,3,1,2,4,1,5]$。

现在你想知道，$k$ 秒之后，整个序列的总和是多少。由于答案太大，你只需要输出答案对 $998244353$ 取模的结果。

输入格式

第一行一个正整数 $T$，表示数据组数。

接下来 $T$ 组数据，每组数据一行两个整数 $n,k$。

输出格式

对于每组数据，输出一行一个整数，代表该组数据的答案对 $998244353$ 取模的结果。

3
5 1
1 14
5 14

21
1
190

数据范围

• 对于 $30\%$ 的数据，$1 \le T \le 200$，$1 \le n,k \le 200$；
• 对于 $60\%$ 的数据，$n \le 200$；
• 对于 $100\%$ 的数据，$1 \le T \le 10^6$，$1 \le n, \sum n \le 10^6$，$1 \le k \le 10^{18}$。