You are given a sequence $$$a$$$ of length $$$n$$$ and a positive integer $$$m$$$. Each element of $$$a$$$ is an integer in the range $$$[0, m]$$$.

A sequence $$$a$$$ is considered good if and only if the following two conditions hold:

$$$a_1 \lt a_2 \lt a_3 \lt \ldots \lt a_n$$$, and
$$$\frac{1}{\operatorname{lcm}(a_1,a_2)}+\frac{1}{\operatorname{lcm}(a_2,a_3)}+\ldots+\frac{1}{\operatorname{lcm}(a_{n-1},a_n)}+\color{red}{\frac{1}{\operatorname{lcm}(a_n,a_1)}}\ge1$$$.$$$^{\text{∗}}$$$

You need to replace all zeros in $$$a$$$ with integers from the range $$$[1, m]$$$. Calculate the number of different ways to replace the zeros such that the resulting sequence $$$a$$$ is good.

Print the answer modulo $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$The Least common multiple ($$$\operatorname{lcm}$$$) of two positive integers is the smallest positive integer that is a multiple of both. For example, $$$\operatorname{lcm}(2,3)=6, \operatorname{lcm}(4,6)=12$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n\le m \le 3000$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le m$$$).

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$3000$$$.

Output

For each test case, output a single integer — the number of ways to complete the sequence so that it becomes good, modulo $$$998\,244\,353$$$.

Note

In the first test case, there are $$$2$$$ ways to replace the zeros such that the sequence becomes good:

$$$[1, 2, 3, 6]$$$: The sum is $$$\frac{1}{\operatorname{lcm}(1, 2)} + \frac{1}{\operatorname{lcm}(2, 3)} + \frac{1}{\operatorname{lcm}(3, 6)} + \frac{1}{\operatorname{lcm}(6, 1)} = \frac{1}{2} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} = 1$$$.
$$$[1, 2, 4, 6]$$$: The sum is $$$\frac{1}{\operatorname{lcm}(1, 2)} + \frac{1}{\operatorname{lcm}(2, 4)} + \frac{1}{\operatorname{lcm}(4, 6)} + \frac{1}{\operatorname{lcm}(6, 1)} = \frac{1}{2} + \frac{1}{4} + \frac{1}{12} + \frac{1}{6} = 1$$$.

In the second test case, the initial sequence is $$$[2, 1]$$$. Since $$$2 \not \lt 1$$$, the strictly increasing condition is not met, so the answer is $$$0$$$.

In the fourth test case, the sequence is fixed to be $$$[0, 0, 6, 0, 0]$$$ with $$$m=6$$$. The third element is $$$6$$$. Since the sequence must be strictly increasing and elements cannot exceed $$$6$$$, we would need $$$6 \lt a_4 \lt a_5 \le 6$$$, which is impossible.

LCM is Legendary Counting Master

Examples