AND Subsequence

3.2

4 votes
, Algorithms, Bitmask, Bit manipulation, Linear Search
Problem

You are given an array having integers and an integer . Find the length of the longest non-empty subsequence of the array such that the Bitwise AND of the elements of the subsequence is greater than or equal to . Print  if no such subsequence exists.

A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

Input format

  • The first line of input contains an integer  denoting the number of test cases. The description of each test case is as follows:
  • The first line of each test case contains two integers  and .
  • The second line of each test case contains integers .

Output format

For each test case, print  if no subsequence satisfies the given condition. Otherwise, print the length of the longest non-empty subsequence in a separate line.

Constraints

 

Sample Input
3
3 2
1 2 3
5 3
6 1 7 4 3
3 5
1 3 4


Sample Output
2
3
-1
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
  • In the first test case, it is optimal to take  in the chosen subsequence because .
  • In the second test case, it is optimal to take in the chosen subsequence because .
  • In the third test case, it is impossible to choose any non-empty subsequence that satisfies the given conditions.
Editor Image

?