给定一个长度为 $n$ 的数组，其中只包含正整数。

现在你可以多次将数组中的所有数字同时加 1。请找出使数组的最大公约数（gcd）大于 1 所需执行的最少操作次数，如果无法做到，则输出 -1。

注意，如果你想将其中一个数字加 1，你必须同时将所有数字都加 1。

输入格式

输入文件的第一行包含一个整数 $T$ ($1 \le T \le 20$)，表示测试用例的数量。

接下来有 $2 \times T$ 行，每两行表示一个测试用例。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。

每个测试用例的第二行包含 $n$ 个整数，范围在 $[1, 10^9]$ 之间。

输出格式

你需要输出恰好 $T$ 行。

对于每个测试用例，首先打印 Case d:（$d$ 表示测试用例的编号）。然后输出一个整数表示答案。如果不可能，则输出 -1。

样例

输入 1

3
1
2
5
2 5 9 5 7
5
3 5 7 9 11

输出 1

Case 1: 0
Case 2: -1
Case 3: 1

说明

• 样例 1：你不需要做任何操作，因为它的 gcd 已经大于 1。
• 样例 2：无法得到满足条件的数组。
• 样例 3：你只需要将所有数字加 1，使得该数组的 gcd 为 2。