F. Ценные карточки
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В своём любимом кафе Kmes захотел в очередной раз отведать селёдку под шубой. Раньше ему бы не доставило труда сделать это, однако кафе недавно выдвинуло новую политику покупки.

Теперь для её совершения Kmes надо решить следующую задачу: перед ним на стол выкладывают $$$n$$$ карточек с ценами на разные позиции, на $$$i$$$-й карточке написано число $$$a_i$$$, среди этих цен нет целого положительного числа $$$x$$$.

Kmes просят разбить эти карточки на минимальное количество плохих отрезков (так, чтобы каждая карточка принадлежала ровно одному отрезку). Плохим считается такой отрезок, что в нём нельзя выбрать подмножество карточек с произведением, равным $$$x$$$. Все отрезки, на которые Kmes разобьёт карточки, должны быть плохими.

Формально, отрезок $$$(l, r)$$$ плохой, если не существует индексов $$$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} = 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$$$.

Выходные данные

Для каждого набора входных данных выведите минимальное количество плохих отрезков.

Пример
Входные данные
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