There is a complete graph containing $n$ vertices, the weight of the $i$-th vertex is $w_i$.
The length of edge between vertex $i$ and $j$ $(i \neq j)$ is $\lfloor \sqrt{|w_i - w_j|} \rfloor$.
Calculate the length of the shortest path from $1$ to $n$.

The first line of the input contains an integer $T$ $(1 \le T \le 10)$ denoting the number of test cases.
Each test case starts with an integer $n$ $(1 \le n \le 10 ^ 5)$ denoting the number of vertices in the graph.
The second line contains $n$ integers, the $i$-th integer denotes $w_i$ $(1 \le w_i \le 10 ^ 5)$.

For each test case, print an integer denoting the length of the shortest path from $1$ to $n$.