给定 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$。您可以对它们执行以下操作:
- 选择任意元素 $$$a_i$$$ ($$$1 \le i \le n$$$) 并将其除以 $$$2$$$ (向下舍入)。换句话说,您可以将任何选定的元素 $$$a_i$$$ 替换为值 $$$\left \lfloor \frac{a_i}{2}\right\rfloor$$$ (其中 $$$\left \lfloor x \right\rfloor$$$ 是向下舍入实数 $$$x$$$)。
输出要使整数序列严格递增(即满足条件 $$$a_1 \lt a_2 \lt \dots \lt a_n$$$ 必须完成的最小操作数)。或者确定不可能获得这样的序列。请注意,元素不能交换。唯一可能的操作如上所述。
例如,让 $$$n = 3$$$ 并给出数字序列 $$$[3, 6, 5]$$$。然后对其执行两个操作就足够了:
- 写入数字 $$$\left \lfloor \frac{6}{2}\right\rfloor = 3$$$ 而不是数字 $$$a_2=6$$$ 并得到序列 $$$[3, 3, 5]$$$;
- 然后将 $$$a_1=3$$$ 替换为 $$$\left \lfloor \frac{3}{2}\right\rfloor = 1$$$ 并得到序列 $$$[1, 3, 5]$$$。
结果序列严格递增,因为 $$$1 \lt 3 \lt 5$$$。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入中测试用例的数量。
测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 30$$$)。
每个测试用例的第二行恰好包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^9$$$)。
输出
对于每个测试用例,在单独的行上打印一个数字 - 对序列执行的最小操作数,以使其严格递增。如果无法获得严格递增的序列,则打印“-1”。
示例
输入 #1
7 3 3 6 5 4 5 3 2 1 5 1 2 3 4 5 1 1000000000 4 2 8 7 5 5 8 26 5 21 10 2 5 14
输出 #1
2 -1 0 0 4 11 0
注意
语句中分析了第一个测试用例。
在第二个测试用例中,不可能获得严格递增的序列。
在第三个测试用例中,序列已经严格递增。