题目描述

Eve 有一个长度为 $n$ 的数组 $a$ 以及一个常数 $m\ge 2$，他知道对于任意的 $1\leq i\leq n$，都有 $2\leq a_i\leq m$。

Eve 觉得数组里一定要有全部相等的元素，所以他想通过以下操作把数组里的元素变得全部相等：

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

请帮助 Eve 求出最少操作多少次能够使得数组里元素全部相等，如果无论多少次操作都不能达成目标，则输出 $-1$。

输入格式

第一行一个整数 $T$ 表示数组组数，对于每组数据：

第一行两个正整数 $n,m$。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$。

输出格式

对于每组数据，如果能使得数组元素全相等，输出一行一个非负整数表示最小操作次数，否则输出一行 -1。

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

0
1

样例解释 1

对于第二组数据，取t=4操作一次即可使数组元素全变为4。

数据范围

对于 $30\%$ 的数据，$\sum n\leq 20$，$m\leq 20$。

对于 $60\%$ 的数据，$\sum n\leq 3\times 10^5$，$m\leq 1000$。

对于 $100\%$ 的数据，$1\leq T\leq 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$。