Sakurako's Birthday

Today is Sakurako's birthday, so you decided to make a good present. You think that the best present will be an array of $n$ equal integers. Unfortunately, you couldn't find such an array. But you are smart, so you can change any element in the array by exactly $k$. In other words, if you have an array $a$, you can choose integer $i$ ($1\le i\le n$) and replace $a_i$ with $a_i-k$ or $a_i+k$. You want to make Sakurako happy, so decide whether you can make an array to be of equal integers.

For example, if you found an array $[10,16,12,10,20]$ with $k=2$, you can make all elements equal to $12$. To do this, add $k$ to the first and fourth elements $(a_1+k=10+2=12)$, subtract $k$ from the second element two times $(s_2-2\cdot k=16-2\cdot 2=12)$, don't change the third element and subtract $k$ from the last element four times ($a_5-4\cdot k=20-4\cdot 2=12$).

Input

The first line contains one integer $t$ ($1\le t\le 10^5$) — the number of such arrays.

Each array is described in two lines.

The first line contains two integers $n$ and $k(1\le n\le 2\cdot 10^5;1\le k\le 10^9)$.

The second line contains $n$ integers $a_1,\dots ,a_n$ ($1\le a_i\le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each array, output "Yes" if Sakurako will be happy or "No" otherwise.

Examples

Note

The first case was explained in the statement.

The second case has answer "Yes", because you can make all numbers equal to $123$.

The third case has answer "No", because it can be proven that the fifth element cannot be equal to any other element of the array after any number of operations.

Scoring

1. ($3$ points): $k=2$;

2. ($8$ points): $a_i\le 100$ for all arrays;

3. ($18$ points): $n\le 1000$ for all arrays; It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

4. ($21$ points): without additional restrictions.