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:
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$$$.
53 54 2 12 11 15 502 3 5 2 34 100000000060 30 1 12 10000000001000000000 2
3 1 0 595458194 200000000
In the first test case, the possible arrays $$$b$$$ are:
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.
Name |
---|