Description

The total amount of money in Xiaoxi’s red packet is defined as follows:

Consider all $K$-tuples where every element is a positive integer and $\le N$. The total amount is the product of the least common multiples of all these $K$-tuples.

However, his uncle does not have that much money, so the result should be taken modulo $998244353$.

Xiaoxi computed it in $10^{-16}$ seconds, but he wants to verify whether it is correct, so he came to you (don’t ask why he doesn’t just open the red packet and check).

In other words, you only need to compute:

$$\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$$

It is guaranteed that $K>1$. Here, ${\rm lcm}(i_1,i_2...i_K)$ denotes the least common multiple of $i_1,i_2...i_K$.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, the number of test cases.

The next $T$ lines each contain two integers $N, K$, representing one query.

Output Format

Output $T$ lines, each containing one integer, the answer modulo $998244353$.

2
2 2
3 2

8
7776

Hint

For the first test case in the sample, the problem asks for ${\rm lcm}(1,1)\times {\rm lcm}(1,2)\times {\rm lcm}(2,1)\times {\rm lcm}(2,2)$.

Clearly, except for ${\rm lcm}(1,1)=1$, all other results are $2$, so the answer is $1\times2\times2\times2=8$.

Data ID	$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

Problem setter: Do you really think there is that much money? Haha, it is all Zimbabwe dollars inside!

Translated by ChatGPT 5