## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Virus Codeforces Solution 2022

C. Virus
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $n$ houses numbered from $1$ to $n$ on a circle. For each $1\le i\le 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.

• of
Solution Click Below:-  👉

👇👇👇👇👇

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\le t\le {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\le n\le {10}^{9}$$1\le m\le min\left(n,{10}^{5}\right)$) — 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\le {a}_{i}\le 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.