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$ .

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$ .

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$ .

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.