#HTR001G. 随机

随机

Background

出题人:曾铭豪

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

Description

很久很久以前,有一个 BB 进制的世界,在这个异世界中有一只猴子与一台打字机。

打字机上有 BB 个按键,分别标注为 0(B1)0 \sim (B - 1)。猴子喜欢在打字机上随机地按键。在每个单位时间,他会在打字机的所有键中等概率随机选取一个,并且按下这个按键。猴子的生命是无限的,即他可以花无限时间打字。

小明喜欢 kk 的倍数。如果猴子连续按下的若干个按键上的数字可以连成一个 BB 进制下 kk 的倍数,那么小明认为猴子完成了目标。

例如,B=7,k=3B = 7, k = 3,猴子连续按下 1,1,21, \underline{1, 2} 即完成了目标,因为 (12)7=9,9mod3=0(12) _ 7 = 9, 9 \bmod 3 = 0。此时猴子用了 33 个单位时间。

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

Format

Input

输入包含多组数据。

输入的第一行为一个正整数 TT,为测试数据的组数。

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

Output

输出共 TT 行,每行一个整数,为你的答案。为避免精度问题,输出对 998244353998244353 取模。

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

Samples

5
2 2
3 2
4 3
7 3
10 8
2
332748119
374341634
977872021
290088106

Limitation

样例 11 解释

对于第 11 组数据,所有可能的过程如下(下划线标出了所求的 kk 的倍数):

  • 0\underline{0}
  • 1,0\underline{1, 0}
  • 1,1,0\underline{1, 1, 0}
  • 1,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$。

对于第 22 组数据,所有可能的过程如下:

  • 0\underline{0}
  • 1,01, \underline{0}
  • 1,1\underline{1, 1}
  • 1,21, \underline{2}
  • 2\underline{2}

答案为 $\dfrac{2}{3} \times 1 + \dfrac{1}{3} \times {2} = \dfrac{4}{3}$。

对于第 33 组数据,所有可能的过程如下:

  • 0\underline{0}
  • 1,01, \underline{0}
  • 1,1,01, 1, \underline{0}
  • 1,1,1\underline{1, 1, 1}
  • 1,1,21, \underline{1, 2}
  • 1,1,31, 1, \underline{3}
  • 1,2\underline{1, 2}
  • 1,31, \underline{3}
  • 2,02, \underline{0}
  • 2,1\underline{2, 1}
  • 2,2,02, 2, \underline{0}
  • 2,2,12, \underline{2, 1}
  • 2,2,2\underline{2, 2, 2}
  • 2,2,32, 2, \underline{3}
  • 2,32, \underline{3}
  • 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}$。

对于第 44 组数据,答案为 8549\dfrac{85}{49}

对于第 55 组数据,我已经找到了一个美妙的解释,可惜空间太小,写不下。

数据规模

本题共有 2525 个测试点,每个测试点满分 44 分。

对于第 ii 个测试点,

  • i20i \leq 20,则保证测试点中所有 k=ik = i,时间限制 11 秒。
  • 否则,没有特殊限制,时间限制 44 秒。

对于所有数据,保证 T=5,2B998244352,1k22T = 5, 2 \leq B \leq 998244352, 1 \leq k \leq 22