原题链接：

There are nn houses numbered from 11 to nn on a circle. For each 1≤i≤n−11≤i≤n−1, house ii and house i+1i+1 are neighbours; additionally, house nn and house 11 are also neighbours.

Initially, mm of these nn houses are infected by a deadly virus. Each morning, Cirno can choose a house which is uninfected and protect the house from being infected permanently.

Every day, the following things happen in order:

• Cirno chooses an uninfected house, and protect it permanently.
• All uninfected, unprotected houses which have at least one infected neighbor become infected.

Cirno wants to stop the virus from spreading. Find the minimum number of houses that will be infected in the end, if she optimally choose the houses to protect.

Note that every day Cirno always chooses a house to protect before the virus spreads. Also, a protected house will not be infected forever.

Input

The input consists of multiple test cases. The first line contains a single integer tt (1≤t≤1041≤t≤104) — the number of test cases. Description of test cases follows.

The first line of each test case consists of two positive integers n,mn,m (5≤n≤1095≤n≤109, 1≤m≤min(n,105)1≤m≤min(n,105)) — the number of houses on the circle, and the number of houses that are initially infected.

The second line of each test case consists of mm distinct positive integers a1,a2,⋯,ama1,a2,⋯,am (1≤ai≤n1≤ai≤n) — the indices of the houses infected initially.

It is guaranteed that the sum of mm over all test cases does not exceed 105105.

Output

For each test case, output an integer on a separate line, which is the minimum number of infected houses in the end.

Example

input

Copy

8
10 3
3 6 8
6 2
2 5
20 3
3 7 12
41 5
1 11 21 31 41
10 5
2 4 6 8 10
5 5
3 2 5 4 1
1000000000 1
1
1000000000 4
1 1000000000 10 16

output

Copy

7
5
11
28
9
5
2
15

Note

In the first test case:

At the start of the first day, house 33, 66, 88 are infected. Choose house 22 to protect.

At the start of the second day, house 33, 44, 55, 66, 77, 88, 99 are infected. Choose house 1010 to protect.

At the start of the third day, no more houses are infected.

In the second test case:

At the start of the first day, house 22, 55 are infected. Choose house 11 to protect.

At the start of the second day, house 22, 33, 44, 55, 66 are infected. No more available houses can be protected.

思路：

正着求被污染的是挺难的，应该求能被保护的房子的数量

第一步：维护一个差分数组，并排序

第二步：从大到小的遍历差分数组，ve【i】-=4*（m-i-1）指的是由于之前隔离时间的原因，中间的房子已经被污染了的（自己想象个图，可以辅助理解）

第三步：ans维护最大可能保护的房子，ve【i】==1时加1，其它取max（ve【i】-1,0）

代码：

#include
using namespace std;
#define int long long
const int maxj=1e5+100;
int a[maxj];
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);//按要求推导公式
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);//a为add,,w
#endif
	int t;cin>>t;
    while(t--){
        int n,m;cin>>n>>m;
        vector<int>ve;
        for(int i=1;i<=m;++i){
            cin>>a[i];
        }sort(a+1,a+m+1);
 
        for(int i=1;i
            ve.emplace_back(a[i+1]-a[i]-1);
        }  
        ve.emplace_back(a[1]+n-a[m]-1);
 
        sort(ve.begin(),ve.end());
 
        int ans=0;//正难则反，求能保护的房子的个数
        for(int i=ve.size()-1;i>=0;--i){
            // cout<
            ve[i]-=4*(m-i-1);
            
            if(ve[i]==1){
                ans++;
 
            }else{
                ans+=max(0ll,ve[i]-1);
            }
        }cout<'\n';
    }
}