CF1750D.Count GCD

You are given two integers $n$ and $m$ and an array $a$ of $n$ integers. For each $1 \le i \le n$ it holds that $1 \le a_i \le m$.

Your task is to count the number of different arrays $b$ of length $n$ such that:

• $1 \le b_i \le m$ for each $1 \le i \le n$, and
• $\gcd(b_1,b_2,b_3,...,b_i) = a_i$ for each $1 \le i \le n$.

Here $\gcd(a_1,a_2,\dots,a_i)$ denotes the greatest common divisor (GCD) of integers $a_1,a_2,\ldots,a_i$.

Since this number can be too large, print it modulo $998\,244\,353$.

给你两个整数 $n$ 和 $m$，以及一个长度为 $n$ 的整数数组 $a$。对每个 $1 \le i \le n$，满足 $1 \le a_i \le m$。

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

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

其中，$\gcd(a_1,a_2,\dots,a_i)$ 表示整数 $a_1,a_2,\ldots,a_i$ 的最大公约数（GCD）。

由于该数目可能非常大，请输出其对 $998\,244\,353$ 取模的结果。

Each test consist of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$, $1 \le m \le 10^9$) — the length of the array $a$ and the maximum possible value of the element.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le m$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ across all test cases doesn't exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case, print a single integer — the number of different arrays satisfying the conditions above. Since this number can be large, print it modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——即满足上述条件的不同数组的个数。由于该数可能很大，请输出其对 $998\,244\,353$ 取模的结果。

In the first test case, the possible arrays $b$ are:

• $[4,2,1]$;
• $[4,2,3]$;
• $[4,2,5]$.

In the second test case, the only array satisfying the demands is $[1,1]$.

In the third test case, it can be proven no such array exists.

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

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

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

在第三个测试用例中，可以证明不存在这样的数组。