VegiCat possiede un'azienda con $n$ dipendenti divisi in $k$ squadre non vuote. I dipendenti vivono lungo una strada rettilinea, rappresentata da una retta numerica. VegiCat vuole organizzare due punti di ritrovo per loro.

VegiCat divide le squadre in due insiemi, $A$ e $B$, con ogni squadra in esattamente un insieme. Sceglie un punto di ritrovo per ciascun insieme in una qualsiasi coordinata reale. Tutti i dipendenti della stessa squadra devono recarsi allo stesso punto di ritrovo. Ogni squadra nell'insieme $A$ va al punto di ritrovo per $A$, e ogni squadra nell'insieme $B$ va al punto di ritrovo per $B$. Uno dei due insiemi può essere vuoto.

Sia $S_A$ l'elenco delle posizioni delle case di tutti i dipendenti delle squadre in $A$, e si definisca $S_B$ in modo analogo per $B$. Ogni dipendente viene contato separatamente, anche quando le posizioni delle case si ripetono.

Per un elenco $S = (x_1, x_2, \ldots, x_m)$ di posizioni delle case, la distanza totale minima che questi dipendenti devono percorrere per raggiungere un unico punto di ritrovo è

$$M(S) = \min_{p \in \mathbb{R}} \sum_{j=1}^{m} |x_j - p|.$$

Si definisca $M(S) = 0$ quando $S$ è vuoto. Aiuta VegiCat a minimizzare $M(S_A) + M(S_B)$ tra tutti i modi possibili di dividere le squadre nei due insiemi.

Input

La prima riga contiene un intero $T$ ($1 \le T \le 3 \cdot 10^5$), il numero di casi di test. Segue la descrizione dei casi di test.

La prima riga di ciascun caso di test contiene due interi $n$ e $k$ ($1 \le k \le n \le 3 \cdot 10^5$), che indicano rispettivamente il numero di dipendenti e il numero di squadre.

Ciascuna delle successive $k$ righe descrive una squadra. La $i$-esima riga contiene un intero $m_i$ ($1 \le m_i \le n$), il numero di dipendenti nella squadra $i$, seguito da $m_i$ interi $x_{i,1}, \ldots, x_{i,m_i}$ ($1 \le x_{i,j} \le 10^7$), le posizioni delle loro case. La somma di tutti gli $m_i$ in un caso di test è $n$.

Le posizioni delle case possono ripetersi e possono essere fornite in qualsiasi ordine.

È garantito che la somma di $n$ su tutti i casi di test non supera $3 \cdot 10^5$.

Output

Per ciascun caso di test, stampa un intero — la minima distanza totale di spostamento possibile.

Esempi

Input 1

2
4 2
2 1 3
2 8 10
8 3
3 4 12 1
2 3 2
3 9 8 10

Output 1

4
15

Note

Nel primo caso di test, VegiCat manda la squadra $1$ a un punto di ritrovo nella posizione $1$ e la squadra $2$ a un punto di ritrovo nella posizione $8$. I dipendenti di ciascuna squadra percorrono una distanza totale di $2$, ottenendo come risposta $4$.

Nel secondo caso di test, VegiCat sceglie i punti di ritrovo in $3$ e $9$. Manda le squadre $1$ e $2$ al primo punto di ritrovo, e la squadra $3$ al secondo. I dipendenti delle squadre $1$, $2$ e $3$ percorrono distanze totali rispettivamente di $12$, $1$ e $2$, ottenendo come risposta $15$.