Given positive integers $n, P$ and a sequence $a_{1\cdots n}$ of length $n$, determine whether there exists a multiplicative function $f(x)$ that satisfies the following conditions:

• The domain and codomain of $f(x)$ are the set of positive integers.
• $f(x)$ is non-strictly monotonically increasing on its domain.
• $\forall x\in [1,n], f(x)\bmod P = a_x$.

Input

This problem contains multiple test cases.

The first line contains two positive integers $T$ and $ID$, representing the number of test cases and the ID of the current test suite, respectively. Specifically, $ID=0$ in the sample.

Each test case is provided as follows:

The first line contains two positive integers $n$ and $P$, as defined above.

The second line contains $n$ non-negative integers, where the $i$-th integer represents $a_i$, as defined above.

Please note that some test cases in this problem have large input sizes, so fastread.cpp is provided in the additional files as a fast I/O template.

To use it, simply paste the template into your code. When read() is called, it will read an integer from the standard input stream and return it. Do not mix this with other input methods. It is guaranteed that the input part of the standard solution is implemented using this template.

If you still do not understand how to use this template, you can check sample.cpp in the additional files, which provides an example implementation; completing this code will suffice.

Output

For each test case, output a single line containing YES if a valid $f(x)$ exists, otherwise output NO.

Please note that you must use uppercase English letters.

Examples

Input 1

3 0
3 5
1 4 4
4 2023
1 2 2 2
5 2023
1 2 10 11 12

Output 1

YES
NO
NO

Note 1

This test suite contains three test cases.

For the first test case, let $f(x)=x^2$. It can be verified that $f(x)$ is a valid non-strictly monotonically increasing multiplicative function that satisfies the conditions. Also, $f(1)\bmod 5={\color{red}1}, f(2)\bmod 5={\color{red}4}, f(3)\bmod 5 = 9\bmod 5={\color{red}4}$, which meets the requirements.

For the second test case, it can be proven that no such valid $f(x)$ exists. For example, if $f(1)=1, f(2)=f(3)=f(4)=2$, then we can obtain $f(6)=f(12)=4$, so $f(7)=f(10)=4, f(5)=2$, thus ${\color{red}f(15)}=f(3)f(5)=4\ {\color{red}

For the third test case, it can also be proven that no such valid $f(x)$ exists. For example, if $f(1)=1, f(2)=2, f(3)=10, f(4)=11, f(5)=12$, then it can be proven that $f(6)=20\le f(7)\le f(10)=24$, while $f(12)=110, f(14)\le 24\times 2=48, {\color{red}f(14)

Due to space limitations, a complete proof of the non-existence of $f(x)$ for the last two test cases cannot be provided in the problem statement.

Constraints

For $100\%$ of the data, $1\leq T\leq 20, 1\le n

It is guaranteed that $\sum n, \sum P\le 10^7$ for each test suite.

This problem uses bundled testing, and the evaluation will bind dependencies according to the logical relationships of the special constraints for each test suite.

The scores and special constraints for each test suite are as follows:

Special Property A: It is guaranteed that if a valid $f(x)$ exists, then there exists a valid $f(x)$ that is a strictly monotonically increasing completely multiplicative function satisfying $\forall x\le n, f(x)

Special Property B: It is guaranteed that if a valid $f(x)$ exists, then there exists a valid $f(x)$ that is a strictly monotonically increasing completely multiplicative function.

Special Property C: It is guaranteed that if a valid $f(x)$ exists, then there exists a valid $f(x)$ that is strictly monotonically increasing.

Special Property D: It is guaranteed that $n=500$, and each $a_i$ is independently and uniformly randomly generated in $[0, P)$. It is also guaranteed that there are exactly $3$ test cases in this test suite.