题目背景

在“星港远征计划”中，补给中心会按照固定规则生产一批标准零件。
第 $k$ 轮生产时，第 $1$ 个零件的编号为 $Bk+C$，之后每个零件的编号依次增加 $D$，共生产 $N$ 个零件。
由于不同批次的零件要进入同一套联锁系统，工程师关心前 $N+1$ 个批次产物编号乘积之间共有的公共因子究竟是多少。

现在，请你求出这些批次乘积的最大公约数，并对指定模数取模。

题目描述

给定正整数 $N,B,C,D$。

对于每个非负整数 $k$，定义

$$a_k=(Bk+C)(Bk+C+D)(Bk+C+2D)\cdots(Bk+C+(N-1)D)$$

也就是说，$a_k$ 是一个首项为 $Bk+C$、公差为 $D$、共 $N$ 项的等差数列所有项的乘积。

请你求出

$$\gcd(a_0,a_1,a_2,\ldots,a_N)$$

对 $998244353$ 取模后的结果。

共有 $T$ 组测试数据，需要分别求解。

---

输入格式

输入从标准输入给出，格式如下：

T
case1
case2
...
caseT

每组测试数据的格式为：

N B C D

---

输出格式

输出 $T$ 行。

第 $i$ 行输出第 $i$ 组测试数据的答案。

---

样例 #1

输入

3
3 1 1 1
4 2 2 6
2026 3 22 216

输出

6
128
114347907

说明

对于第一组测试数据：

$$(a_0,a_1,a_2,a_3) = (1\times2\times3,\ 2\times3\times4,\ 3\times4\times5,\ 4\times5\times6) = (6,24,60,120)$$

因此它们的最大公约数为 $6$。

---

数据范围

• $1 \le T \le 10^5$
• $1 \le N,B,C,D \le 10^6$
• 输入中的所有值均为整数