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$.