暂无测试数据。

题目描述

若 $a$ 能被 $b$ 整除，则说明 $b$ 是 $a$ 的约数(也叫因数)。定义一个数列的 $\text{lcm}$ 值为数列中所有数的最小公倍数。

定义一个数 $n$ 的约数(因数)排列为一个数列，数列中的每一项均为 $n$ 的约数(因数)。两个约数排列不同当且仅当两个排列的项数不同（如 $\{1,2\}$ 与 $\{1,2,2\}$ 为不同的两个 $2$ 的约数数列），或者某一个对应位置的数不同（如 $\{1,2,1,3\}$ 与 $\{1,1,2,3\}$ 为不同的两个 $6$ 的约数数列）。

对于给定的 $n,m$，我们只关心恰好含有 $m$ 个数的 $n$ 的约数数列，我们想知道，这些只含有 $m$ 个数的 $n$ 的约数数列的 $\text{lcm}$ 的总和是多少。

输入格式

多组数据，第一行一个整数 $T$，表示有 $T$ 次询问。

下面 $T$ 行每行两个整数 $n,m$，意义如上所述。

输出格式

输出 $T$ 行，第 $i$ 行的数字表示第 $i$ 次询问的答案。

由于答案可能很大，所以你只需要输出对 $998244353$ 取模后的结果。

数据范围

对于 $20\%$ 的数据，满足 $n\leq 10,m\leq 8$。

对于 $40\%$ 的数据，满足 $n\leq 10^{12},m\leq 10$。

对于另外 $20\%$ 的数据，满足 $n=2$。

对于 $100\%$ 的数据，满足 $1\leq T\leq 10,1\leq n\leq 10^{12},1\leq m\leq 10^{18}$。

1
4 2

27

1
5 3

36

1
6 1

12