题目描述

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

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

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

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

输入格式

本题有多组数据

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

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

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

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$ 。