Problem

In a kingdom there are * cells (numbered 1 to P) built to form a straight line segment. Cells number i and i+1 are adjacent, and *ers in adjacent cells are called "neighbours." A wall with a window separates adjacent cells, and neighbours can communicate through that window.

All *ers live in peace until a *er is released. When that happens, the released *er's neighbours find out, and each communicates this to his other neighbour. That *er passes it on to his other neighbour, and so on until they reach a *er with no other neighbour (because he is in cell 1, or in cell P, or the other adjacent cell is empty). A *er who discovers that another *er has been released will angrily break everything in his cell, unless he is bribed with a gold coin. So, after releasing a *er in cell A, all *ers housed on either side of cell A - until cell 1, cell P or an empty cell - need to be bribed.

Assume that each * cell is initially occupied by exactly one *er, and that only one *er can be released per day. Given the list of Q *ers to be released in Qdays, find the minimum total number of gold coins needed as bribes if the *ers may be released in any order.

Note that each bribe only has an effect for one day. If a *er who was bribed yesterday hears about another released *er today, then he needs to be bribed again.

Input

The first line of input gives the number of cases, N. N test cases follow. Each case consists of 2 lines. The first line is formatted as

P Q

where P is the number of * cells and Q is the number of *ers to be released.
This will be followed by a line with Q distinct cell numbers (of the *ers to be released), space separated, sorted in ascending order.

Output

For each test case, output 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 as bribes.

Limits

1 ≤ N ≤ 100
Q ≤ P
Each cell number is between 1 and P, inclusive.

Small dataset

1 ≤ P ≤ 100
1 ≤ Q ≤ 5

Large dataset

1 ≤ P ≤ 10000
1 ≤ Q ≤ 100

Sample

Note

In the second sample case, you first release the person in cell 14, then cell 6, then cell 3. The number of gold coins needed is 19 + 12 + 4 = 35. If you instead release the person in cell 6 first, the cost will be 19 + 4 + 13 = 36.

题目大意：

t 组测试数据，n个人在*，要放出m个人，每放出一个人，他周围的人（两边连续的直到碰到空的*或者尽头）都要贿赂1个钱，问最少的总花费

解题思路：

记忆化dp，dp(i,j) 表示从 编号 a[i] ~ a[j] 不包含 a[i] 与 a[j] 的子树的花费

状态转移方程 d[i][j]=min(dp(i,k)+dp(k,j)+(a[j]-a[i]-2),d[i][j])

注意，一开始添加哨兵，0号位与n+1号位

 void solve()

 {

     a[]=;a[m+]=n+;

     for(int i=;i<=n;i++)

         dp[i][i+]=;

     for(int w=;i+w<=m+;i++)

     {

         for(int i=;i+w<=m+;i++)

         {

             int j=i+w,t=inf;

             for(int k=i+;k<j;k++)

                 t=min(t,dp[i][k]+dp[k][j]);

             dp[i][j]=t+a[j]-a[i]-;

         }

     }

     cout<<dp[][m+]<<endl;

 }

 #include"iostream"

 #include"cstdio"

 #include"cstring"

 #include"algorithm"

 using namespace std;

 const int inf=1e9;

 const int ms=;

 int a[ms],dp[ms][ms],n,m,p;

 int solve(int i,int j)

 {

     if(dp[i][j]!=inf)

         return dp[i][j];

     if(i+>=j)

         return ;

     for(int k=i+;k<j;k++)

         dp[i][j]=min(solve(i,k)+solve(k,j)+(a[j]-a[i]-),dp[i][j]);

     return dp[i][j];

 }

 int main()

 {

     int t;

     p=;

     cin>>t;

     while(t--)

     {

         cin>>n>>m;

         a[]=;a[m+]=n+;

         for(int i=;i<=m;i++)

             cin>>a[i];

         //fill(dp,dp+sizeof(dp)/sizeof(int),inf);  出错

         for(int i=;i<=m+;i++)

             for(int j=;j<=m+;j++)

                 dp[i][j]=inf;

         int ans=solve(,m+);

         cout<<"Case #"<<p++<<": "<<ans<<endl;

     }

     return ;

 }