ANDrew's Challenge

4

2 votes
Problem

Announcement: There was some issue with input for python users. It has been fixed.

Andrew has just studied how bitwise operations work and has thought of a challenge. You are given an array a of size n, and an integer x. In one step, you can replace a[i] by a[i]&x, where & represents the bitwise AND operation, for any 0in1. You need to find the minimum number of steps in which you can make atleast two elements of the array the same, i.e. the minimum number of steps after which i,j,  0i<j<n and a[i]=a[j]. Can you complete Andrew's challenge?

Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains two space seperated integers, n and x, which denote the size of the array and the given integer respectively.

The second line of each test case contains n space seperated integers, which denote the elements of the array.

Output

Print T lines, with each line containing a single integer denoting the minimum number of steps required to complete Andrew's challenge for the corresponding test case. Print 1 if the challenge cannot be completed for that test case.

Constraints

1T1001n1051x1051a[i]105

Problem Author: Aryan Agarwal

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

In the first test case, two elements are already the same, hence answer is zero.

In the second test case, note that 5&1 = 1 so minimum 1 step is required

Editor Image

?