题目描述

对于正整数 $i$ 和 $j$，定义 $f_i(j)$ 为最大的整数 $k$，使得 $i^k$ 能整除 $j$。如果对于某个数 $j$，有 $f_6(j) > f_7(j)$，则称 $j$ 是特殊数。例如，$6$ 是特殊数，但 $67$ 和 $7$ 都不是。

现在给定一个包含 $n$ 个正整数的数组 $a$。你可以进行若干次操作，每次操作将数组的每个元素都加 $1$。

你的任务是找出最少需要多少次操作，才能使数组 $a$ 中所有元素同时变为特殊数。如果无论如何都无法做到，请输出 $-1$。

输入格式

第一行输入一个整数 $t$，表示测试用例数，$1 \leq t \leq 10^4$。

每个测试用例的第一行输入一个整数 $n$，$1 \leq n \leq 2 \times 10^5$。

每个测试用例的第二行输入 $n$ 个正整数 $a_1, a_2, \dots, a_n$，$1 \leq a_i \leq 10^9$。

所有测试用例中 $n$ 的总和不超过 $2 \times 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]$。

由 ChatGPT 5 翻译

来源

Codeforces 2200H，英文题名 Six Seven。