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