← 返回题目列表

Codeforces · 2200/H

H. 六七

中文机器翻译题面 查看原题

对于正整数 $$$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$$$。

示例

输入
复制

4
3
1 2 3
2
25 67
8
6 6 12 18 24 36 42 84
1
9557351

输出
复制

-1
5
12
7

注意

在第一个测试用例中,所有元素不能同时变得特殊。

在第二个测试用例中,执行$$$5$$$操作会得到数组$$$[30,72]$$$,其元素都是特殊的。

在第四个测试用例中,经过 $$$7$$$ 操作后,数组变为 $$$[9557358]$$$。