说明

本题与 Hack of Multiply 2 Divide 2 之间没有依赖关系。

Frank_DD 有一个长度为 $n$ 的序列 $a$。 每次操作，他可以选择一个数 $a_i$ ($1 \le i \le n$) 并将其变为 $a_i \cdot 2$ 或 $\lfloor \frac{a_i}{2} \rfloor$。 Frank_DD 想知道将序列 $a$ 变为非递减序列所需的最少操作次数。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 5$)，表示测试用例的数量。接下来是 $T$ 个测试用例。 每个测试用例中： 第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示序列 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^5$)，表示序列 $a$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示将序列 $a$ 变为非递减序列所需的最少操作次数。

样例

输入格式 1

2
7
6 3 3 4 10 8 2
10
9 9 4 7 3 10 10 8 4 3

输出格式 1

4
11

说明

在第一个测试用例中，我们可以使用至少 4 次操作将序列 $a$ 变为非递减序列： $a_1 = \lfloor \frac{a_1}{2} \rfloor$ $a_5 = \lfloor \frac{a_5}{2} \rfloor$ $a_7 = a_7 \cdot 2$ $a_7 = a_7 \cdot 2$