ikrpprpp 找到一个由整数组成的数组 $$$a$$$。他喜欢正义,所以他想让 $$$a$$$ 公平——也就是说,让它不减。为此,他可以对数组的索引 $$$1 \le i \le n$$$ 执行正义行动,这会将 $$$a_i$$$ 替换为 $$$a_i ^ 2$$$ (位置 $$$i$$$ 的元素与其平方)。例如,如果 $$$a = [2,4,3,3,5,3]$$$ 并且 ikrpprpp 选择对 $$$i = 4$$$ 执行正义行为,则 $$$a$$$ 变为 $$$[2,4,3,9,5,3]$$$。
最少需要多少次正义行为才能使数组不减?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。接下来是测试用例的描述。
对于每个测试用例,第一行包含一个整数 $$$n$$$ — 数组 $$$a$$$ 的大小。第二行包含 $$$n$$$ ($$$1 \le n \le 2 \cdot 10 ^5$$$) 整数 $$$a_1, a_2,\ldots, a_n$$$ ($$$1 \le a_i \le 10 ^ 6$$$)。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot {10}^5$$$。
输出
对于每个测试用例,打印一个整数 - 使数组 $$$a$$$ 非递减所需的正义行为的最小数量。如果无法做到这一点,请打印 $$$-1$$$。
示例
输入 #1
7 3 1 2 3 2 3 2 3 3 1 5 4 1 1 2 3 3 4 3 2 9 16 2 4 2 256 2 4 2 8 11 10010 10009 10008 10007 10006 10005 10004 10003 10002 10001 10000
输出 #1
0 1 -1 0 3 15 55
注意
在第一个测试用例中,不需要执行正义行为。数组本身是公平的!
在第三个测试用例中,可以证明数组不能变成非减的。
在第五个测试用例中,ikrppppppp 可以对索引 3 执行正义行为,然后对索引 2 执行正义行为,最后对索引 3 执行另一正义行为。之后,$$$a$$$ 将变为 $$$[4, 9, 16]$$$。