Given a sorted array containing distinct integers and a number 'key', find the index of the key in the array.
If the key is not present, return the index at which it would be inserted considering that we need to maintain the sort order.

Expected Time Complexity: O(log n)

Examples

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

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

Array: [1, 2, 3, 4, 5]
Number: -100
Answer: 0

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

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 the index of the first occurrence of the key in the array or the index to insert the number (if not present) for each test case.

Sample Input

4
5 3
1 2 3 4 5
4 4
1 2 3 5
5 -100
1 2 3 4 5
5 6
1 2 3 4 5

Expected Output

2
3
0
5

Constraints

1 <= T <= 100

1 <= n <= 104

-106 <= Ai <= 106

-106 <= key <= 106