给定一个大小为 $n$ 的数组 $a$ 以及两个整数 $m_1$ 和 $m_2$。如果数组 $p$ 满足以下条件，我们称其为“好”的：

• $p$ 是一个大小为 $n$ 的排列，由 $1$ 到 $n$ 的不同整数组成。
• 数组 $a_{p_1} \bmod m_1, a_{p_2} \bmod m_1, \dots, a_{p_n} \bmod m_1$ 是一个非递减数组。
• 数组 $a_{p_1} \bmod m_2, a_{p_2} \bmod m_2, \dots, a_{p_n} \bmod m_2$ 是一个非递增数组。

请计算“好”的排列 $p$ 的数量，结果对 $998244353$ 取模。

输入格式

输入包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 10\,000$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n, m_1$ 和 $m_2$ ($1 \le n \le 100\,000, 1 \le m_1, m_2 \le 10^4$)，分别表示数组长度和两个模数。

下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示该数组。

保证所有测试用例的 $n$ 之和不超过 $100\,000$。

输出格式

对于每个测试用例，输出一个整数，表示问题的答案对 $998244353$ 取模的结果。

样例

输入 1

3
5 2 3
1 2 3 4 10
4 2 4
1 2 3 4
3 8 9
1 1 1

输出 1

2
0
6

说明

在第一个测试用例中，有两个“好”的排列：$p = [2, 4, 5, 1, 3]$ 和 $p = [2, 5, 4, 1, 3]$。

在第二个测试用例中，不存在“好”的排列。

在第三个测试用例中，所有 $6$ 个排列都是“好”的。