Given a sorted array and a number key, return whether the key is present in the array or not.

Expected Time Complexity: O(log n)

Examples

Array: [1, 2, 3, 3, 3, 4, 4, 5]
Number: 2
Answer: true

Array: [1, 2, 3, 3, 3, 4, 4, 5]
Number: 6
Answer: false

Testing

Input Format

First-line contains an integer ‘T’ denoting the number of test cases.

For each test case the input has two lines:

• Two space-separated integers ‘n’ and 'key' denoting the length of the array and the number to be searched respectively.
• n space-separated integers denoting the elements of the array.

Output Format

T lines each contain true or false denoting the answer for each test case.

Sample Input

2
8 2
1 2 3 3 3 4 4 5
8 6
1 2 3 3 3 4 4 5

Expected Output

true
false

Constraints

1 <= T <= 100

1 <= n <= 104

-106 <= Ai <= 106

-106 <= key <= 106