Nasser's Parity Array Transformation

Input

The first line contains a single integer $t$ (1 \le t \le 10^4) — the number of test cases.

The first line of each test case contains two integers $n,x$ (1 \le n \le 2 \cdot 10^5, 1 \le x \le 10^9) — the size of the array and the target value.

The second line contains $n$ integers a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9) — the elements of the array.

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

Output

For each test case, output a single integer — the minimum number of operations, or $-1$ if it's impossible to make all elements equal to $x$.

Examples

Note

In the first test case, a=[1,3,2] and x=4.

• Increase a_1 twice: [1,3,2] \to [2,3,2] \to [3,3,2]

• Increase a_3 once: [3,3,2] \to [3,3,3]

• Increase the entire array (all odd): [3,3,3] \to [4,4,4]

• Total: 4 operations

Scoring

1. Subtask $1$ ($10$ points) : (1 \le \sum n \le 10)

2. Subtask $2$ ($15$ points) : (1 \le \sum n \le 100,1 \le x \le 10^{6})

3. Subtask $3$ ($25$ points) : (1 \le \sum n \le 5000,1 \le x \le 10^{9})

4. Subtask $4$ ($200$ points) : No additional constraints.