Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

greedy

implementation

sortings

*1200

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Virus

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere are $$$n$$$ houses numbered from $$$1$$$ to $$$n$$$ on a circle. For each $$$1 \leq i \leq n - 1$$$, house $$$i$$$ and house $$$i + 1$$$ are neighbours; additionally, house $$$n$$$ and house $$$1$$$ are also neighbours.

Initially, $$$m$$$ of these $$$n$$$ 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 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. Description of test cases follows.

The first line of each test case consists of two positive integers $$$n, m$$$ ($$$5 \leq n \leq 10^9$$$, $$$1 \leq m \leq \min(n, 10^5)$$$) — 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 $$$m$$$ distinct positive integers $$$a_1, a_2, \cdots , a_m$$$ ($$$1 \leq a_i \leq n$$$) — the indices of the houses infected initially.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$10^5$$$.

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

810 33 6 86 22 520 33 7 1241 51 11 21 31 4110 52 4 6 8 105 53 2 5 4 11000000000 111000000000 41 1000000000 10 16

Output

7 5 11 28 9 5 2 15

Note

In the first test case:

At the start of the first day, house $$$3$$$, $$$6$$$, $$$8$$$ are infected. Choose house $$$2$$$ to protect.

At the start of the second day, house $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$7$$$, $$$8$$$, $$$9$$$ are infected. Choose house $$$10$$$ 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 $$$2$$$, $$$5$$$ are infected. Choose house $$$1$$$ to protect.

At the start of the second day, house $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$ are infected. No more available houses can be protected.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/07/2023 12:53:14 (l2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|