问题描述

在遥远的数学王国里，有一座被智慧之光笼罩的山峰——数论峰。这座山峰上居住着各式各样的数学精灵，它们以解开数字的奥秘为乐。

数论峰中一共有 $m$ 只数论精灵，每只精灵每天都会选择一个权值为 $[1,n]$ 中数字作为一天的幸运数，不同的精灵可以选择相同的数字作为幸运数。

当一天中所有数论精灵的幸运数的最小公倍数恰好为 $n$ 时，数论峰中的古老大门将打开。

聪明的你想知道，有多少方案使得所有数论精灵的幸运数的最小公倍数恰好为 $n$ ，答案对 $998244353$ 取模。

两种方案不同当且仅当有一只精灵的幸运数不同。

输入格式

本题共有 $T$ 组数据。

输入第一行，包含一个正整数，表示 $T$。

之后对于每组数据，输入 $1$ 行，包含 $2$ 个正整数 $n,m$。

输出格式

输出共 $T$ 行，每行输出 $1$ 个整数，表示最终答案，答案对 $998244353$ 取模。

4
6 2
3 4
5 6
7 8

9
15
63
255

样例解释1

当 $n=6,m=2$ 时，合法的解有 $(2,3),(3,2),(1,6),(6,1),(2,6),(3,6),(6,2),(6,3),(6,6)$​。

5
4 5
5 4
98 97
100000 9982443
123454 2

211
15
306665342
947591178
27

见下发文件中的 lcm/lcm3.in

见下发文件中的 lcm/lcm3.ans

见下发文件中的 lcm/lcm4.in

见下发文件中的 lcm/lcm4.ans

提示

• 对于 $20\%$ 的数据，$1 \leq n,m \leq 5,1 \leq T \leq 10$。

• 对于 $40\%$ 的数据，$1 \leq n,m \leq 500,1 \leq T \leq 10$​。

• 对于另外 $10\%$ 的数据，$n$​​ 为质数。

• 对于另外 $30\%$ 的数据，$m=2$。

• 对于 $100\%$ 的数据，$1 \leq T \leq 10^3,1 \leq n,m \leq 10^9$。