Background

出题人：曾铭豪

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

Description

很久很久以前，有一个 $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$ 个单位时间。

小明很好奇，猴子完成目标所需要的期望时间是多少单位？他请你帮助他求解这个问题。

Format

Input

输入包含多组数据。

输入的第一行为一个正整数 $T$，为测试数据的组数。

接下来 $T$ 行，每行两个正整数 $B, k$，意义如上所述。

Output

输出共 $T$ 行，每行一个整数，为你的答案。为避免精度问题，输出对 $998244353$ 取模。

容易证明答案可以表示为有理数 $\dfrac{x}{y}$，你的输出即为最小的非负整数 $t$ 使得 $x \equiv ty \pmod{998244353}$。保证这样的整数 $t$ 存在。

Samples

5
2 2
3 2
4 3
7 3
10 8

2
332748119
374341634
977872021
290088106

Limitation

样例 $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$。