Paprika 喜欢排列。她有一个数组 $$$a_1, a_2, \dots, a_n$$$。她想让数组成为整数 $$$1$$$ 到 $$$n$$$ 的排列。
为了达到这个目的,她可以对数组进行操作。在每个操作中,她可以选择两个整数 $$$i$$$ ($$$1 \le i \le n$$$) 和 $$$x$$$ ($$$x > 0$$$),然后执行 $$$a_i := a_i \bmod x$$$ (即将 $$$a_i$$$ 替换为 $$$a_i$$$ 除以 $$$x$$$ 的余数)。在不同的操作中,选择的$$$i$$$和$$$x$$$可以不同。
确定使数组成为整数 $$$1$$$ 到 $$$n$$$ 的排列所需的最少操作数。如果不可能,则输出$$$-1$$$。
排列是由从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 不同整数组成的数组,按任意顺序排列。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列($$$2$$$ 在数组中出现两次),$$$[1,3,4]$$$ 也不是排列($$$n=3$$$ 但数组中有 $$$4$$$)。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$。 ($$$1 \le a_i \le 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出使数组成为整数排列 $$$1$$$ 到 $$$n$$$ 所需的最少操作数,如果不可能,则输出 $$$-1$$$。
示例
输入 #1
4 2 1 7 3 1 5 4 4 12345678 87654321 20211218 23571113 9 1 2 3 4 18 19 5 6 7
输出 #1
1 -1 4 2
注意
对于第一个测试,最小化操作数量的唯一可能的操作顺序是:
- 选择$$$i=2$$$, $$$x=5$$$。执行 $$$a_2 := a_2 \bmod 5 = 2$$$。
对于第二个测试,不可能获得从 $$$1$$$ 到 $$$n$$$ 的整数排列。