En unas ruinas recién descubiertas, la arqueóloga Liora encontró el mosaico de Oridion. Originalmente era una única franja de piedra de longitud $n$, pero el paso del tiempo la dejó dividida en $k$ fragmentos. El fragmento $i$ tiene longitud $a_i$.

Para conservar el hallazgo, Liora debe restaurar la franja usando un antiguo cemento de unión. El cemento solo reacciona con teselas de longitud uno, y las ruinas cuentan con una herramienta que puede desprender una tesela de ese mismo tamaño.

En un movimiento puede realizar una de estas acciones:

1. Elegir un fragmento de longitud $a_i \ge 2$ y desprender de él una tesela de longitud $1$. El fragmento se reemplaza por dos fragmentos de longitudes $1$ y $a_i - 1$.
2. Elegir dos fragmentos distintos, uno de longitud $a_i$ y otro de longitud $1$, y unirlos con el cemento. Ambos se reemplazan por un único fragmento de longitud $a_i + 1$.

Después de cada acción, todos los fragmentos que no participaron permanecen intactos. ¿Cuál es la menor cantidad de movimientos con la que Liora puede restaurar el mosaico como una sola franja de longitud $n$?

La primera línea contiene un entero $t$ ($1 \le t \le 10^4$), el número de casos de prueba.

Cada caso de prueba contiene dos líneas:

• La primera contiene dos enteros $n$ y $k$ ($2 \le n \le 10^9$, $2 \le k \le 10^5$): la longitud original de la franja y la cantidad de fragmentos encontrados.
• La segunda contiene $k$ enteros $a_1, a_2, \ldots, a_k$ ($1 \le a_i \le n - 1$), las longitudes de los fragmentos. Se garantiza que $a_1 + a_2 + \cdots + a_k = n$.

Se garantiza que la suma de $k$ entre todos los casos de prueba de una entrada no supera $2 \times 10^5$

Para cada caso de prueba, imprime el mínimo número de movimientos necesarios para restaurar el mosaico.