Bribe the Prisoners (Large)

A kingdom keeps its prison cells, numbered 1 to $P$, in one straight line. Cells $i$ and $i+1$ are adjacent, and the prisoners in two adjacent cells are called neighbours. The wall between two adjacent cells has a window, so neighbours talk to each other.

The prison stays quiet until a prisoner is released. When that happens, the neighbours of the released prisoner learn about it, and each one passes the news to his other neighbour. That prisoner passes it on to his own other neighbour, and so on, until the news reaches a prisoner who has no other neighbour, because he sits in cell 1, or in cell $P$, or the cell on his other side is empty. A prisoner who learns that someone was released smashes everything in his cell, unless you give him one gold coin. So releasing the prisoner in cell $A$ forces you to bribe every prisoner on both sides of cell $A$, going outward until you reach cell 1, cell $P$, or an empty cell.

Every cell starts with exactly one prisoner, and you release only one prisoner per day. Given the cell numbers of the $Q$ prisoners to release over $Q$ days, find the smallest total number of gold coins you need when you may choose the release order freely.

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

The first line has 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 has the $Q$ cell numbers of those prisoners, all different, space separated and sorted in ascending order.

Limits

• $1 \le N \le 100$
• $1 \le P \le 10000$
• $1 \le Q \le 100$
• $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 bribes.

Take $P = 20$ with releases in cells 3, 6 and 14. Releasing cell 14 first, then cell 6, then cell 3 costs 19 + 12 + 4 = 35 gold coins. Releasing cell 6 first costs 19 + 4 + 13 = 36, which is worse.