Water The Garden

지금은 겨울이고, Max는 정원에 물을 줄 때가 되었다고 생각했다.

정원은 1부터 n까지 번호가 매겨진 n개의 연속된 화단으로 나타낼 수 있다. k개의 화단에는 수도꼭지가 있으며(i-th 수도꼭지는 화단 xi에 있다), 이 수도꼭지를 틀면 이웃한 화단에 물을 공급하기 시작한다. 화단 xi의 수도꼭지를 틀면, 일 초가 지난 뒤 화단 xi에 물이 공급된다. 이 초가 지난 뒤에는 구간 $[xi - 1, xi + 1]$의 화단에 물이 공급된다(해당 화단이 존재하는 경우). j초가 지난 뒤에는(j는 정수이다) 구간 [xi - (j - 1), xi + (j - 1)]의 화단에 물이 공급된다(해당 화단이 존재하는 경우). 각 초가 흐르는 도중에는 아무것도 변하지 않으므로, 예를 들어 2.5초가 지난 뒤 구간 $[xi - 2.5, xi + 2.5]$에 물이 공급된다고 말할 수 t없다. 그 시점에는 구간 $[xi - 2, xi + 2]$에만 물이 공급되어 있다.

테스트 1의 정원. 흰색은 수도꼭지가 없는 화단을, 빨간색은 수도꼭지가 있는 화단을 나타낸다. 수도꼭지를 튼 뒤 2초가 지난 시점의 테스트 1의 정원. 흰색은 아직 물이 공급되지 않은 화단을, 파란색은 물이 공급된 화단을 나타낸다.

Max는 모든 수도꼭지를 동시에 틀려고 하며, 이제 일부 수도꼭지를 튼 뒤 정원 전체에 물이 공급될 때까지 지나야 하는 최소 시간이 몇 초인지 궁금해한다. Max가 답을 구할 수 있도록 돕는다!

첫 번째 줄에 해결해야 할 테스트 케이스의 수를 나타내는 정수 하나 t가 주어진다 (1 ≤ t ≤ 200).

이어서 t개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 각각 화단의 수와 수도꼭지의 수를 나타내는 두 정수 n과 k이 주어진다 (1 ≤ n ≤ 200, 1 ≤ k ≤ n).

다음 줄에는 k개의 정수 xi가 주어진다 (1 ≤ xi ≤ n) — i-th 수도꼭지의 위치이다. 각 에 대해 조건 xi - 1 < xi가 성립함이 보장된다.

모든 테스트 케이스에 걸친 n의 합은 200을 초과하t 않음이 보장된다.

해킹에서는 t = 1로 설정해야 한다는 점에 유의한다.

각 테스트 케이스마다 Max가 일부 수도꼭지를 튼 뒤 정원 전체에 물이 공급될 때까지 지나야 하는 최소 시간을 초 단위로 나타내는 정수 하나를 출력한다.

첫 번째 예제는 3개의 테스트로 이루어진다.

1. 화단이 5개 있고, 화단 3에 수도꼭지가 있다. 이 수도꼭지를 틀면 1초가 지난 뒤에는 화단 3에만 물이 공급되고, 2초가 지난 뒤에는 화단 $[1, 3]$에 물이 공급되며, 3초가 지난 뒤에는 모든 곳에 물이 공급된다.
2. 화단이 3개 있고, 각 화단에 수도꼭지가 하나씩 있다. 수도꼭지를 모두 틀면 1초가 지난 뒤 모든 곳에 물이 공급된다.
3. 화단이 4개 있고, 화단 1에만 수도꼭지가 하나 있다. 예를 들어 화단 4에 물을 공급하는 데 4초가 걸린다.