La fattoria di Farmer John è costituita da $N$ campi $(1 \leq N \leq 10^5)$, comodamente numerati $1 \ldots N$. Tra questi campi ci sono $M$ sentieri bidirezionali $(0 \leq M \leq 10^5)$, ciascuno dei quali collega una coppia di campi.

La fattoria contiene due stalle, una nel campo $1$ e l'altra nel campo $N$. Farmer John vuole assicurarsi che sia possibile camminare tra le due stalle seguendo una sequenza di sentieri. È disposto a costruire fino a due nuovi sentieri per raggiungere questo obiettivo. A causa della disposizione dei campi, il costo per costruire un nuovo sentiero tra i campi $i$ e $j$ è $(i-j)^2$.

Aiuta Farmer John a determinare il costo minimo necessario affinché le stalle $1$ e $N$ diventino raggiungibili l'una dall'altra.

Input

Ogni caso di test in input contiene $T$ sottocasi ($1\le T\le 20$), che devono essere tutti risolti correttamente per superare il caso in input.

La prima riga dell'input contiene $T$, dopo cui seguono $T$ sottocasi di test.

Ogni sottocaso di test inizia con due interi, $N$ e $M$. Seguono poi $M$ righe, ciascuna contenente due interi $i$ e $j$, che indicano un sentiero tra due campi distinti $i$ e $j$. È garantito che ci sia al massimo un sentiero tra due campi qualsiasi e che la somma di $N+M$ su tutti i sottocasi di test sia al massimo $5 \cdot 10^5$.

Output

Stampa $T$ righe. L'$i$-esima riga deve contenere un solo intero che indica il costo minimo per l'$i$-esimo sottocaso di test.

Esempi

Input 1

2
5 2
1 2
4 5
5 3
1 2
2 3
4 5

Output 1

2
1

Nota

Nel primo sottocaso di test, è ottimale collegare i campi $2$ e $3$ con un sentiero e i campi $3$ e $4$ con un altro sentiero.

Nel secondo sottocaso di test, è ottimale collegare i campi $3$ e $4$ con un sentiero. Non serve un secondo sentiero.

Sottoproblemi

• Il caso di test 2 soddisfa $N \le 20$.
• I casi di test 3-5 soddisfano $N \le 10^3$.
• I casi di test 6-10 non hanno vincoli aggiuntivi.

Autore del problema: Nick Wu