有价值的卡片

时间限制：4 秒
空间限制：512 MB

在 Kmes 最喜欢的咖啡馆里，他又想尝尝鲱鱼配皮草大衣。以前这不难，但咖啡馆最近推出了新的购买政策。

现在为了完成购买，Kmes 需要解决以下问题：在他面前摆着 $n$ 张卡片，每张卡片上有一个价格，第 $i$ 张卡片上的整数为 $a_i$，题目保证这些价格中不存在正整数 $x$。

Kmes 需要把这些卡片划分成尽可能少的坏段（每张卡片恰属于一段）。一个段被称为“坏的”，如果不可能从中选出一个子集（子序列）使得其乘积等于 $x$。所有分段都必须是坏的。

形式化地，段 $(l, r)$ 是坏的，如果不存在下标 $i_1 < i_2 < \dots < i_k$ 满足 $l \le i_1, i_k \le r$，且 $a_{i_1} \cdot a_{i_2} \dots \cdot a_{i_k} = x$。

请帮助 Kmes 求出最少需要划分成几个坏段，以便享用他最爱的菜肴。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^3$）—— 测试数据组数。

每组数据的第一行包含两个整数 $n$ 和 $x$（$1 \le n \le 10^5$，$2 \le x \le 10^5$）—— 卡片数量以及目标整数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 2 \cdot 10^5$，$a_i \neq x$）—— 卡片上的价格。

保证所有测试数据的 $n$ 之和不超过 $10^5$。

输出格式

对于每组测试数据，输出一个整数 —— 最少需要划分的坏段数量。

样例输入

8
6 4
2 3 6 2 1 2
9 100000
50000 25000 12500 6250 3125 2 4 8 16
5 2
1 1 1 1 1
8 6
4 3 4 3 4 3 4 3
7 12
6 11 1 3 11 10 2
10 5
2 4 4 2 4 4 4 3 1 1
7 8
4 6 5 1 2 4 1
8 27
3 9 17 26 2 20 9 3

样例输出

3
2
1
1
2
1
3
3