Inverse Divisible Permutation

2 secs 1024 MB
mel1's icon mel1

問題文

正整数 NN が与えられます.
(1,2,,N)(1, 2, \ldots, N) の順列 P=(P1,P2,,PN)P = (P_1, P_2, \ldots, P_N) であって, 次の条件をみたすものの個数を 998244353998244353 で割った余りを求めてください.

  • 2iN2\leqq i \leqq N をみたす任意の整数 ii について, PiP_iii の約数である.

11つの入力ファイルにつき, TT個のテストケースを解いてください.

制約

  • 1T201\leqq T \leqq 20
  • 1N1051\leqq N \leqq 10^5

入力

入力は以下の形式で標準入力から与えられる.

  TT
  case1case_1
  case2case_2
  \vdots
  caseTcase_T

各ケースは以下の形式で与えられる.

  NN

出力

TT行出力せよ. ii行目には ii 番目のテストケースへの答えを出力せよ.

サンプル

入力例1
2
3
120
出力例1
3
1313

N=3N=3のとき, (1,2,3),(2,1,3),(3,2,1)(1, 2, 3), (2, 1, 3), (3, 2, 1) の3つが条件をみたします.

提出


Go (1.21)