В своём любимом кафе 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 определить минимальное количество плохих отрезков, чтобы насладиться любимым блюдом.