Valuable Cards
Contest: Codeforces Round 957 (Div. 3)
Difficulty rating: 1900
Tags: brute force, dp, greedy, number theory, two pointers

In his favorite cafe Kmes once again wanted to try the herring under a fur coat. Previously, it would not have been difficult for him to do this, but the cafe recently introduced a new purchasing policy.

Now, in order to make a purchase, Kmes needs to solve the following problem: $$$n$$$ cards with prices for different positions are laid out in front of him, on the $$$i$$$-th card there is an integer $$$a_i$$$, among these prices there is no whole positive integer $$$x$$$.

Kmes is asked to divide these cards into the minimum number of bad segments (so that each card belongs to exactly one segment). A segment is considered bad if it is impossible to select a subset of cards with a product equal to $$$x$$$. All segments, in which Kmes will divide the cards, must be bad.

Formally, the segment $$$(l, r)$$$ is bad if there are no indices $$$i_1 < i_2 < \ldots < i_k$$$ such that $$$l \le i_1, i_k \le r$$$, and $$$a_{i_1} \cdot a_{i_2} \ldots \cdot a_{i_k} = x$$$.

Help Kmes determine the minimum number of bad segments in order to enjoy his favorite dish.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases.

The first line of each set of input data gives you $$$2$$$ integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 10^5, 2 \le x \le 10^5$$$) — the number of cards and the integer, respectively.

The second line of each set of input data contains $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 2 \cdot 10^5, a_i \neq x$$$) — the prices on the cards.

It is guaranteed that the sum of $$$n$$$ over all sets of test data does not exceed $$$10^5$$$.

Output format:
For each set of input data, output the minimum number of bad segments.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Example input:
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

Example output:
3
2
1
1
2
1
3
3

Editorial:
Let's consider the greedy algorithm "take as long as you can". Let's prove that it works. In any optimal division, if we take the first segment of non-maximum length, we will not violate the criteria if we transfer one element from the second segment to the first. Therefore, the given greedy algorithm is correct.
Now let's figure out how to quickly understand if the segment can be extended. First, find all divisors of the number $$$x$$$. If the number $$$a_i$$$ is not a divisor of it, then it cannot be included in any set of numbers whose product is equal to $$$x$$$, so we can simply add it to the segment. If $$$a_i$$$ is a divisor, we need to somehow learn to understand whether it, in combination with some other divisors, gives the number $$$x$$$ on the segment. We will maintain a set of divisors that are products of some numbers in the segment. To update the set when adding $$$a_i$$$, we will go through all the divisors of this set and for each divisor $$$d$$$ add $$$d \cdot a_i$$$ to the set. If we added the number $$$x$$$ to the set, $$$a_i$$$ will already be in the next segment and we need to clear the set.
P. S.: About implementation details and runtime. If you maintain the set in a set structure, then we get a runtime of $$$O(n \cdot d(x) \cdot \log(d(x)))$$$, where $$$d(x)$$$ is the number of divisors of $$$x$$$. Instead of a set, you can use, for example, a global array $$$used$$$ of size $$$10^5 + 1$$$, as well as maintain a vector of reachable divisors. Using these structures, you can achieve a runtime of $$$O(n \cdot d(x))$$$.