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 0≤i≤n−1. 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, 0≤i<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
1≤T≤1001≤n≤1051≤x≤1051≤a[i]≤105
Problem Author: Aryan Agarwal
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