在他最喜欢的咖啡馆里,Kmes 再次想尝试一下披着毛皮大衣的鲱鱼。以前,他做到这一点并不困难,但咖啡馆最近推出了新的采购政策。
现在,为了进行购买,Kmes 需要解决以下问题:$$$n$$$ 卡片上放置了不同位置的价格,在第 $$$i$$$ 卡片上有一个整数 $$$a_i$$$,这些价格中没有整数 $$$x$$$。
Kmes 被要求将这些卡划分为最少数量的坏段(以便每张卡恰好属于一个段)。如果无法选择乘积等于 $$$x$$$ 的卡牌子集,则认为该分段是坏的。 Kmes 分牌的所有部分都一定是坏的。
形式上,如果没有索引 $$$i_1 < i_2 < \ldots < i_k$$$ 使得 $$$l \le i_1、i_k \le r$$$ 和 $$$a_{i_1} \cdot a_{i_2} \ldots \cdot a_{i_k} = ,则段 $$$(l, r)$$$ 是坏的x$$$。
帮助 Kmes 确定坏片段的最少数量,以便享受他最喜欢的菜肴。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^3$$$) — 测试用例的数量。
每组输入数据的第一行给出 $$$2$$$ 整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le n \le 10^5, 2 \le x \le 10^5$$$) — 分别是卡片的数量和整数。
每组输入数据的第二行包含 $$$n$$$ 整数 $$$a_i$$$ ($$$1 \le a_i \le 2 \cdot 10^5, a_i \neq x$$$) — 卡片上的价格。
保证所有测试数据集的$$$n$$$总和不超过$$$10^5$$$。
输出
对于每组输入数据,输出坏段的最小数量。
示例
输入 #1
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
输出 #1
3 2 1 1 2 1 3 3