AT_arc216_d.[ARC216D] GCD of Product of Arithmetic Progression

正整数 $ N, B, C, D $ が与えられます．

非負整数 $ k $ に対し，整数 $ a_k $ を初項 $ Bk+C $ ，公差 $ D $ ，項数 $ N $ の等差数列の全項の積，すなわち $ a_k=(Bk+C)(Bk+C+D)(Bk+C+2D)\dots(Bk+C+(N-1)D) $ で定義します．

$ a_0,a_1,a_2,\ldots,a_N $ の最大公約数を $ 998244353 $ で割った余りを求めてください．

$ T $ 個のテストケースが与えられるので，それぞれについて答えてください．

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

$ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $

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

$ N $ $ B $ $ C $ $ D $

$ T $ 行出力せよ． $ i $ 行目には $ \mathrm{case}_i $ に対する答えを出力せよ．

Sample Explanation 1

$ 1 $ つ目のテストケースについて， $ (a_0, a_1, a_2, a_3) = (1 \times 2 \times 3, 2 \times 3 \times 4, 3 \times 4 \times 5, 4 \times 5 \times 6) = (6, 24, 60, 120) $ であり，これらの最大公約数は $ 6 $ です．

Constraints

• $ 1\leq T\leq 10^5 $
• $ 1\leq N,B,C,D\leq 10^6 $
• 入力は全て整数