题目描述

翁老师有一个长度为 $n$ 的数组 $a$ 以及一个常数 $m\geq 2$，对于任意的 $1\leq i\leq n$ 都有 $2\leq a_i\leq m$。

翁老师喜欢元素全部相等的数组，因此他想通过以下操作把数组里的元素变得全部相等：

• 选定一个整数 $t$，满足 $2\leq t\leq m$。然后令每一个 $a_i$ 都变为 $\gcd(a_i,t)$。
  • 其中 $\gcd(x,y)$ 为 $x,y$ 的最大公约数，例如 $\gcd(2,4)=6,\gcd(15,21)=3$。

请你求出最少几次操作可以使得数组里元素全部相等，若无论多少次都不能达到目标，输出 $-1$。

输入格式

本题有多组数据

第一行输入一个整数 $t$ 代表测试数据组数。每一组数据：

• 第一行输入两个正整数 $n,m$。
• 第二行输入 $n$ 个空格隔开的整数分别代表 $a_1,a_2,\ldots,a_n$。

输出格式

对于每一组数据：输出一个整数，代表答案。

每一组数据的结果换行隔开。

3
3 343
343 343 343
5 100
4 8 12 16 20
4 5
2 3 4 5

0
1
2

提示

样例解释

• 第二组数据：令 $t=4$，可以使得所有数字都变为 $4$，因此只需要操作 $1$ 次。
• 第三组数据：令 $t=2$，四个数字分别变为 [2, 1, 2, 1]，继续令 $t=3$，可以使得四个数组均为 $1$，可以证明不可能 $1$ 次操作使得四个数字均相等。

数据范围

对于 $100\%$ 的数据，$1 \le t \le 10^5$，$1\leq n\leq 10^5$，$\sum n\leq 3\times 10^5$，$2\leq m\leq 10^6$，$2\leq a_i\leq m$。

• 子任务 1（30 分）：保证 $\sum n\leq 20,m\leq 20$。
• 子任务 2（30 分）：保证 $m\leq 1000$。
• 子任务 3（40 分）：无特殊限制。