TSP

$10^{18}$개의 정점으로 이루어진 트리가 있습니다. 이 트리에는 $2 \le i \le 10^{18}$인 $i$에 대해, $i$번째 정점과 $\left\lfloor \frac{i}{2} \right \rfloor$번째 정점을 잇는 간선이 있습니다.

이 트리에서 $K$개의 정점 $v_1, v_2, \cdots, v_K$가 주어집니다. 임의의 정점에서 시작해서 주어진 $K$개의 정점을 각각 한 번 이상 방문하는 경로 중, 가장 짧은 경로의 길이를 구하세요.

첫 줄에 테스트케이스의 수 $T$가 주어집니다. $(1 \le T \le 10\,000)$

각 테스트케이스의 첫 줄에 정점의 수 $K$가 주어집니다. $(2 \le K \le 100\,000)$

둘째 줄에는 주어진 정점의 번호 $v_1, v_2, \cdots, v_K$가 공백으로 구분되어 주어집니다. 모든 $v_i$는 서로 다릅니다. $(1 \le v_i \le 10^{18})$

주어지는 모든 입력은 정수입니다.

모든 테스트케이스에서 $K$의 합이 $100\,000$을 넘지 않습니다.

각 테스트케이스마다 한 줄에 하나씩, 임의의 정점에서 시작해서 주어진 $K$개의 정점을 각각 한 번 이상 방문하는 경로 중, 가장 짧은 경로의 길이를 출력하세요.

길이 $L$인 트리의 경로는 방문한 정점을 차례로 나열한 수열 $p_0, p_1, \cdots, p_L$로 표현되며, $1 \le i \le L$에 대해 $p_{i-1}$과 $p_i$가 서로 간선으로 연결되어 있어야 합니다. 같은 정점 혹은 간선을 여러 번 방문해도 됩니다.