Description

魔理沙的计算器可以进行 $b$ 进制的运算，屏幕上可以显示 $k$ 个数字（不包含小数点）。进行计算后，若某个数字超出了屏幕，就会被直接舍去（例如 $b=10$ 时 $1\div 7=0.142857\cdots$，若屏幕大小为 $4$，那么最终显示为 $0.142$）。

魔理沙用计算器计算了 $1\div n=n'$，再计算 $1\div n'=n''$（$n'$ 和 $n''$ 均为显示在屏幕上的结果）。魔理沙希望知道，有多少个正整数 $n$ 使得 $n=n''$。你只需要输出这个答案对 $998,244,353$ 取模后的结果即可。

Input Format

• 第一行有一个正整数 $T$，表示数据组数。
• 接下来 $T$ 行，每行有两个正整数 $b,k$，分别表示计算器的进制、屏幕上能显示的数字个数。

Output Format

• 输出共 $T$ 行。
• 每行输出一个整数。第 $i$ 行的整数表示第 $i$ 组数据中合法的 $n$ 的总数对 $998,244,353$ 取模后的结果。

3
4 2
5 3
12 99

3
3
19503

Hint

样例解释

• 对于第一组询问，符合条件的数（转换成十进制）为 $1,2,4$。
• 对于第二组询问，符合条件的数（转换成十进制）为 $1,5,25$。

数据范围及约定

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|}\hline \textbf{subtask}&\textbf{分值} & \bm{b\le} & \bm {k\le } & \textbf{特殊性质} & \textbf{subtask 依赖} \cr\hline 1 & 20 & 10 & 7 & - &-\cr\hline 2 & 20 & 10^5 & 2 & k=2&-\cr\hline 3 & 10 & 10^5 & 3 & k=3&- \cr\hline 4 & 50& 10^5 & 500 & -&1,2,3\cr\hline \end{array}$$

对于 $100\%$ 的数据，满足 $1\le T\le 10$，$2\le b\le 10^5$，$1\le k\le 500$。