题目背景

魔理沙是普通而平凡的魔法使。在解决了大大小小的异变后，她终于攒足了足够多的钱在香霖堂里购置了一台 $\verb!Carno!$ 计算器，用来计算魔女之汤各种配料的含量之比。

魔理沙早就听闻灵梦通过河童重工网络入手了一部 $\verb!Casio!$ 计算器，来计算神社的香火钱，却买到了假货，最多只能显示整数部分（下取整）。而魔理沙的这部可以精确到小数点后面若干位（下取整）的计算器。更高级的是，这部计算器还可以支持其他的进制，其强大的功能高出了灵梦一大截。因此作为灵梦真挚的朋友，魔理沙希望向灵梦表达真挚的遗憾之情。

正当魔理沙打算出发之时，她发现虽然 $\verb!Carno!$ 计算器不会导致一些特别大的误差，但是在计算除法时仍然会出现一定的问题。考虑将计算器的进制调整为 $10$ 进制，而计算器屏幕上最多可以显示 $5$ 位数字（小数点不计入显示位数）。比如，魔理沙希望计算 $1\div 3$ 的值，那么真正显示在屏幕上的则是：

$$0.3333$$

按照道理上来讲，$1\div(1\div 3)$ 结果应当等于 $3$。但出乎意料的是，当魔理沙输入 $1\div 0.3333$ 后，得到的结果却是：

$$3.0003$$

这当然只是一个个例。当魔理沙计算 $1\div(1\div 4)$ 时，屏幕上显示出了正确的数字。

为了防止在表达遗憾之情的时候自己的计算器也出了漏子，魔理沙希望找到有多少个数字使得计算出的结果是正确的，因此她向你求助了。

题目描述

魔理沙的计算器可以进行 $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$ 取模后的结果即可。

输入格式

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

输出格式

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

3
4 2
5 3
12 99

3
3
19503

提示

样例解释

• 对于第一组询问，符合条件的数（转换成十进制）为 $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$。