对于正整数 $$$i$$$ 和 $$$j$$$,将 $$$f_i(j)$$$ 定义为最大整数 $$$k$$$,使得 $$$i^k$$$ 除以 $$$j$$$。考虑数字$$$j$$$ 特别 如果 $$$f_6(j) \gt f_7(j)$$$。例如,$$$6$$$ 是 特别,但 $$$67$$$ 和 $$$7$$$ 不是。
给定一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。在一次操作中,必须将数组中的每个元素增加 $$$1$$$。
你的任务是找到生成 $$$a$$$ 中的所有元素所需的最少操作数 特别 同时,或判定不可能。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$),测试用例的数量。
对于每个测试用例,第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$)。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数:同时使所有元素变得特殊的最小操作数,如果不可能,则输出 $$$-1$$$。
示例
输入复制
431 2 3225 6786 6 12 18 24 36 42 8419557351
输出复制
-15127
注意
在第一个测试用例中,所有元素不能同时变得特殊。
在第二个测试用例中,执行$$$5$$$操作会得到数组$$$[30,72]$$$,其元素都是特殊的。
在第四个测试用例中,经过 $$$7$$$ 操作后,数组变为 $$$[9557358]$$$。