F. Valuable Cards
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.
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\).
For each set of input data, output the minimum number of bad segments.