T183642 随机（2021 CoE III F）

> 无限猴子定理：让一只猴子在打字机上随机地按键，当按键时间达到无穷时，几乎必然能够打出任何给定的文字。 > —— 摘自维基百科

很久很久以前，有一个 $B$ 进制的世界，在这个异世界中有一只猴子与一台打字机。 打字机上有 $B$ 个按键，分别标注为 $0 \sim (B - 1)$。猴子喜欢在打字机上随机地按键。在每个单位时间，他会在打字机的所有键中**等概率**随机选取一个，并且按下这个按键。猴子的生命是无限的，即他可以花无限时间打字。 小明喜欢 $k$ 的倍数。如果猴子**连续**按下的若干个按键上的数字可以连成一个 $B$ 进制下 $k$ 的倍数，那么小明认为猴子完成了目标。 例如，$B = 7, k = 3$，猴子连续按下 $1, \underline{1, 2}$ 即完成了目标，因为 $(12) _ 7 = 9, 9 \bmod 3 = 0$。此时猴子用了 $3$ 个单位时间。 小明很好奇，猴子完成目标所需要的期望时间是多少单位？他请你帮助他求解这个问题。

输入包含多组数据。 输入的第一行为一个正整数 $T$，为测试数据的组数。 接下来 $T$ 行，每行两个正整数 $B, k$，意义如上所述。

输出共 $T$ 行，每行一个整数，为你的答案。为避免精度问题，输出对 $998244353$ 取模。 容易证明答案可以表示为有理数 $\dfrac{x}{y}$，你的输出即为最小的非负整数 $t$ 使得 $x \equiv ty \pmod{998244353}$。保证这样的整数 $t$ 存在。

### 样例 $1$ 解释 对于第 $1$ 组数据，所有可能的过程如下（下划线标出了所求的 $k$ 的倍数）： - $\underline{0}$ - $\underline{1, 0}$ - $\underline{1, 1, 0}$ - $\underline{1, 1, 1, 0}$ - $\cdots$ 答案为 $\dfrac{1}{2} \times 1 + \dfrac{1}{4} \times 2 + \dfrac{1}{8} \times 3 + \dfrac{1}{16} \times 4 + \cdots = 2$。 对于第 $2$ 组数据，所有可能的过程如下： - $\underline{0}$ - $1, \underline{0}$ - $\underline{1, 1}$ - $1, \underline{2}$ - $\underline{2}$ 答案为 $\dfrac{2}{3} \times 1 + \dfrac{1}{3} \times {2} = \dfrac{4}{3}$。 对于第 $3$ 组数据，所有可能的过程如下： - $\underline{0}$ - $1, \underline{0}$ - $1, 1, \underline{0}$ - $\underline{1, 1, 1}$ - $1, \underline{1, 2}$ - $1, 1, \underline{3}$ - $\underline{1, 2}$ - $1, \underline{3}$ - $2, \underline{0}$ - $\underline{2, 1}$ - $2, 2, \underline{0}$ - $2, \underline{2, 1}$ - $\underline{2, 2, 2}$ - $2, 2, \underline{3}$ - $2, \underline{3}$ - $\underline{3}$ 答案为 $\dfrac{2}{4} \times 1 + \dfrac{6}{16} \times 2 + \dfrac{8}{64} \times 3 = \dfrac{1}{2} + \dfrac{3}{4} + \dfrac{3}{8} = \dfrac{13}{8}$。 对于第 $4$ 组数据，答案为 $\dfrac{85}{49}$。 对于第 $5$ 组数据，我已经找到了一个美妙的解释，可惜空间太小，写不下。 ### 数据规模 本题共有 $25$ 个测试点，每个测试点满分 $4$ 分。 对于第 $i$ 个测试点， - 若 $i \leq 20$，则保证测试点中所有 $k = i$，时间限制 $1$ 秒。 - 否则，没有特殊限制，时间限制 $4$ 秒。 对于所有数据，保证 $T = 5, 2 \leq B \leq 998244352, 1 \leq k \leq 22$。