codeforces#P1750D. Count GCD

    ID: 33357 远端评测题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>bitmasksbrute forcecombinatoricsmathnumber theory

Count GCD

Description

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

Input

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

Output

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

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

Note

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.