题目描述

Eve 有一个长度为 n 的数组 a，并知道每个元素满足 2 ≤ a_i ≤ m (m ≥ 2)。Eve 想通过如下操作把数组所有元素变得完全相等：

• 选择一个整数 t (2 ≤ t ≤ m)，把数组中每个元素替换为 gcd(a_i, t)。

请你帮助 Eve 求出最少需要多少次操作才能使数组元素全都相等；如果无论操作多少次都无法做到，输出 -1。

输入格式

T
n m
a1 a2 … an

• 第一行一个整数 T，表示测试数据组数。
• 对于每组数据：
  • 第一行给出 n , m (2 ≤ n ≤ 3×10^5, 2 ≤ m ≤ 10^6)；
  • 第二行给出 n 个整数 a_i (2 ≤ a_i ≤ m)。

数组规模保证

Σ n ≤ 3×10^5

输出格式

对于每组数据，输出一行整数：

• 如果能够把所有元素变得相等，输出最少操作次数；
• 否则输出 -1。

样例

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

0
1

说明

• 第 1 组数据中，本身已全相等，无需操作。
• 第 2 组数据取 t = 4 进行一次操作即可把所有元素都变为 4。