题目描述

给定两个整数 $n$ 和 $m$，以及一个长度为 $n$ 的数组 $a$。对于每个 $1 \le i \le n$，都有 $1 \le a_i \le m$。

你的任务是计算有多少个不同的长度为 $n$ 的数组 $b$ 满足以下条件：

• 对于每个 $1 \le i \le n$，都有 $1 \le b_i \le m$；
• 对于每个 $1 \le i \le n$，都有 $\gcd(b_1, b_2, b_3, \ldots, b_i) = a_i$。

这里 $\gcd(a_1, a_2, \dots, a_i)$ 表示整数 $a_1, a_2, \ldots, a_i$ 的最大公约数。

由于答案可能很大，请输出答案对 $998\,244\,353$ 取模后的结果。

输入格式

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 100$）——表示测试用例的数量。接下来是每组测试用例的描述。

每组测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 2 \cdot 10^5$，$1 \le m \le 10^9$）——数组 $a$ 的长度和元素的最大可能值。

每组测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le m$）——数组 $a$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示满足条件的不同数组的数量。由于答案可能很大，请输出对 $998\,244\,353$ 取模后的结果。

样例

5
3 5
4 2 1
2 1
1 1
5 50
2 3 5 2 3
4 1000000000
60 30 1 1
2 1000000000
1000000000 2

3
1
0
595458194
200000000

提示

样例1解释

在第一个测试用例中，可能的数组 $b$ 有：

• $[4,2,1]$；
• $[4,2,3]$；
• $[4,2,5]$。

在第二个测试用例中，唯一满足条件的数组是 $[1,1]$。

在第三个测试用例中，可以证明不存在满足条件的数组。