A. Make All Elements 0
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ non-negative integers and an integer $$$k$$$.

In one operation you can do:

  • choose two integers $$$l,r(1 \le l \le r \le n)$$$ and a positive integer $$$x(1 \le x \le k)$$$, after that make $$$a_i:=a_i\&x$$$ for all $$$l \le i \le r$$$.

Here $$$\&$$$ denotes the bitwise AND operation.

Find the minimum number of operations to make all elements to zero.

If it's impossible to make all elements to zero, output $$$-1$$$ instead.

Input

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

The first line of each testcase contains two integers $$$n,k$$$ ($$$1 \le n,k \le 10000$$$).

The second line of each testcase contains $$$n$$$ integers $$$a_1,a_2,\ldots, a_n$$$ ($$$0 \le s_i \le 10000$$$).

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

Output

For each test case, print a single integer — the minimum number of operations to make all elements to zero. If it's impossible to make all elements to zero, output $$$-1$$$ instead.

Example
Input
4
1 1
0
4 4
1 3 2 8
4 3
1 3 2 8
8 1
1 5 17 29 1000 11 45 22
Output
0
1
2
-1