AND Subsequence

3.2

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

You are given an array A having N integers and an integer X. Find the length of the longest non-empty subsequence of the array A such that the Bitwise AND of the elements of the subsequence is greater than or equal to X. Print 1 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 T 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 N and X.
  • The second line of each test case contains N integers A1,A2,,AN.

Output format

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

Constraints

1T1041N1051Ai,X<230Sum of N over all test cases does not exceed 3105.

 

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 A2,A3 in the chosen subsequence because A2&A3=2&3=2X=2.
  • In the second test case, it is optimal to take in the chosen subsequence because A1&A3&A3=6&7&4=4X=3.
  • In the third test case, it is impossible to choose any non-empty subsequence that satisfies the given conditions.
Editor Image

?