← 返回题目列表

Codeforces · 1992/F

F. 有价值的卡片

中文机器翻译题面 查看原题

在他最喜欢的咖啡馆里,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