题目描述

Eve 有一个长度为 $n$ 的数组 $a$，以及一个常数 $m\;(m\ge 2)$。 他知道数组满足

[ 2\le a_i\le m,\qquad 1\le i\le n . ]

Eve 觉得数组元素最终必须全部相等，于是他可以重复执行如下操作：

• 任选一个整数 $t$，满足 $2\le t\le m$；
• 把每个元素 $a_i$ 改成 $\gcd(a_i,t)$。

其中 $\gcd(x,y)$ 表示 $x,y$ 的最大公因数（例如 $\gcd(4,6)=2$，$\gcd(15,21)=3$）。

请你帮助 Eve 计算：最少需要多少次操作才能使数组中所有元素相等； 若无论进行多少次操作都无法达成目标，则输出 $-1$。

输入格式

• 第一行一个整数 $T$，表示测试数据组数。
• 对于每组数据：
  1. 第一行两个整数 $n,m$；
  2. 第二行给出 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

对每组数据，输出一行：

• 若可行，输出最小操作次数（非负整数）；
• 否则输出 -1。

数据范围