spoj#NINJA5. K NUMBERS
K NUMBERS
Problem statement:
You are given N numbers from 1 to N. Now, your task is to choose some numbers from the N numbers (including 1 & N) such that no two numbers are consecutive. As this is easy, you are given an extra task. You have to definitely choose K numbers which are given. Find the maximum number of numbers that you can choose in such a way.
Input:
The first line has an integer T, the number of test cases.
Then for each test case, the first line has two integers N and K.
Then the next line has K numbers which you should definitely chooose.
Output:
For each test case, print the maximum number of numbers that you can choose.
Constraints:
1 <= T <= 100
2 <= N <= 2 x 10 ^ 6
1 <= K <= N / 2
1 <= X[1...K] <= N
Sample input:
1
8 2
6 2
Sample output:
4