G. XOR + Constructive = Love
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Litusiano has, yet again, found another 8-pages-long statement. Disappointed with the problemsetters who create such long statements, he has created a problem with a very short statement. Now he has gifted it to you so that you can enjoy a short statement, for once. Unfortunately, Esomer is very evil and he has intercepted Litusiano's gift, adding this whole useless paragraph to annoy Litusiano.

You are given an array $$$a$$$ of length $$$30$$$ and you need to construct a new array $$$b$$$ of minimum length such that:

  • There are at least $$$a_i$$$ elements with bit $$$i$$$ set in their binary representation, for $$$0 \le i \lt 30$$$.
  • The sum of all the elements is $$$s$$$.
  • The bitwise XOR$$$^\dagger$$$ of all the elements is exactly $$$x$$$.

If such an array doesn't exist, output $$$-1$$$ instead.

$$$^\dagger$$$If you don't know what bitwise XOR is, remember that you can use the internet!.

Input

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

On the first line of each test case there are two integers, $$$s$$$ and $$$x$$$, the required sum of all the elements in $$$b$$$ and the required XOR of all the elements in $$$b$$$, respectively. ($$$0 \le s \le 10^{18}$$$; $$$0 \le x \lt 2^{30}$$$).

Then comes a line with $$$30$$$ integers, $$$a_1, a_2, \ldots, a_{30}$$$, each $$$a_i$$$ denotes the minimum number all elements in $$$b$$$ that must have the $$$i$$$-th bit set on their binary representation. ($$$0 \le a_i \le 10^9$$$).

Output

For each test case, if there doesn't exist any array that satisfies the conditions, print $$$-1$$$. Otherwise, print the minimum length of such an array.

Examples
Input
2
9 5
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
9 6
1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Output
2
-1
Input
3
9 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2147483648 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
104 10
5 2 3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Output
2
-1
6
Note

—

Problem idea: Esomer

Problem preparation: Esomer

Ocurrences: Novice 7, Advanced 2