VegiCat è in missione di sminamento. Ci sono $n$ mine su una retta numerica. La mina $i$ si trova alla coordinata intera $a_i$. Le mine sono numerate in ordine di coordinata, quindi $a_1 \le a_2 \le \cdots \le a_n$. Le coordinate delle mine possono ripetersi.

VegiCat testa ogni mina una volta, nell'ordine $1, 2, \ldots, n$. Per la mina $i$, sceglie una coordinata intera $b_i$ come posizione di test, che può essere negativa o zero. L'errore di questo test è $|a_i - b_i|$.

Per ciascun $2 \le i \le n$, viene fornito un intero $l_i$, che specifica la distanza minima richiesta tra le posizioni di test per le mine $i - 1$ e $i$. Queste posizioni devono soddisfare

$$|b_i - b_{i-1}| \ge l_i.$$

Aiuta VegiCat a minimizzare il massimo errore di test; cioè, trova

$$\min_{\substack{b_1, \ldots, b_n \in \mathbb{Z} \\ |b_i - b_{i-1}| \ge l_i \ (2 \le i \le n)}} \left(\max_{1 \le i \le n} |a_i - b_i|\right).$$

Input

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

La prima riga di ciascun caso di test contiene un intero $n$ ($2 \le n \le 10^5$), il numero di mine.

La seconda riga contiene $n$ interi $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$), dove $a_i$ è la coordinata della mina $i$. È garantito che $a_1 \le a_2 \le \cdots \le a_n$.

La terza riga contiene $n - 1$ interi $l_2, l_3, \ldots, l_n$ ($1 \le l_i \le 10^9$), dove $l_i$ è la distanza minima tra le posizioni di test per le mine $i - 1$ e $i$.

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

Output

Per ciascun caso di test, stampa un intero — il minimo valore possibile del massimo errore di test.

Esempi

Input 1

2
2
1 1
1
7
2 6 12 14 14 16 19
11 8 4 2 10 9

Output 1

1
6

Note

Nel primo caso di test, scegliere $b_1 = 1$ e $b_2 = 2$ dà un errore massimo di $1$. Un errore pari a $0$ richiederebbe $b_1 = b_2 = 1$, il che viola il requisito di distanza.

Nel secondo caso di test, una scelta ottimale è $b = [-4, 7, 15, 10, 8, 22, 13]$. Tutte le distanze richieste sono soddisfatte e l'errore massimo è $6$.