Bribe the Prisoners (Small)

A kingdom has $P$ prison cells built in a straight line and numbered 1 to $P$. Cell $i$ and cell $i+1$ are adjacent, and the prisoners in two adjacent cells are neighbours. A wall with a window separates adjacent cells, so neighbours talk to each other through the window.

Everyone stays calm until a prisoner is released. When that happens, both neighbours of the released prisoner find out, and each of them passes the news to his own other neighbour. That prisoner passes it on again, and the news keeps travelling until it reaches a prisoner who has no further neighbour, either because he is in cell 1, or because he is in cell $P$, or because the next cell is already empty. A prisoner who learns that someone was released smashes everything in his cell unless he is handed one gold coin. So releasing the prisoner in cell $A$ forces you to bribe every prisoner on both sides of cell $A$, up to cell 1, up to cell $P$, or up to an empty cell.

Every cell holds exactly one prisoner at the start, and only one prisoner is released per day. Given the $Q$ prisoners to release over $Q$ days, find the smallest total number of gold coins you need if you may choose the release order freely.

A bribe works for one day only. A prisoner bribed yesterday must be bribed again if he hears about another release today.

The first line holds the number of test cases $N$. $N$ test cases follow. Each case takes two lines. The first line is

P Q

where $P$ is the number of prison cells and $Q$ is the number of prisoners to release. The second line holds $Q$ distinct cell numbers, space separated, sorted in ascending order.

Limits

• $1 \le N \le 100$
• $1 \le P \le 100$
• $1 \le Q \le 5$
• $Q \le P$
• Every cell number is between 1 and $P$, inclusive.

For each test case, print one line in the format

Case #X: C

where $X$ is the case number starting from 1, and $C$ is the minimum number of gold coins needed for the bribes.

Take $P = 20$, $Q = 3$ and the cells 3, 6, 14. Releasing cell 14 first, then cell 6, then cell 3 costs $19 + 12 + 4 = 35$. Releasing cell 6 first, then cell 3, then cell 14 costs $19 + 4 + 13 = 36$.