题目背景

新年到了，小僖收到了叔叔寄给他的红包，这个红包里面有很多很多的钱。

题目描述

小僖收到的红包总额是这样的：

所有 $K$ 元组满足每个元素都是正整数且 $\le N$，总额就是这些 $K$ 元组的最小公倍数的乘积。

但由于叔叔并没有那么多的钱，所以结果还要对 $998244353$ 取模。

小僖花了 $10^{-16}$ 秒就算了出来，但他想验证一下是否正确，于是找上了你（别问我为什么他不直接拆开红包看）。

换句话讲，题目只需要你求：

$$\prod_{i_1=1}^N\prod_{i_2=1}^N...\prod_{i_K=1}^N{\rm lcm}(i_1,i_2...i_K)\mod 998244353 $$

保证 $K>1$，其中，${\rm lcm}(i_1,i_2...i_K)$，表示 $i_1,i_2...i_K$ 的最小公倍数。

输入格式

本题有多组数据。

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

接下来 $T$ 行，每行两个数，$N,K$，表示每组询问。

输出格式

$T$ 行，每行一个数，表示答案，记得对 $998244353$ 取模。

2
2 2
3 2

8
7776

提示

对于样例的第一组数据，题目要求求出 ${\rm lcm}(1,1)\times {\rm lcm}(1,2)\times {\rm lcm}(2,1)\times {\rm lcm}(2,2)$。

显然，除了 ${\rm lcm}(1,1)=1$ 以外其它的结果都为 $2$，所以答案为 $1\times2\times2\times2=8$。

数据编号	$N\le$	$K\leq$	$T=$
0	$10$	$5$	$10$
1	$10^6$	$2$	$10^3$
2		$3$
3	$100$	$10^{18}$	$100$
4	$10^5$	$100$	$10^3$
5		$3\times10^8$	$1$
6		$10^{100}$	$10$
7	$10^6$	$10^{18}$	$10^3$
8		$10^{100}$
9

出题人：你真以为有这么多钱，哈哈，里面装的全是津巴布韦币哦！