In one move, Milica can replace the whole string with $$$\texttt{AA} \ldots \texttt{A}$$$. In her second move, she can replace a prefix of length $$$k$$$ with $$$\texttt{BB} \ldots \texttt{B}$$$. The process takes no more than $$$2$$$ operations. The question remains — when can we do better?

In the hint section, we showed that the minimum number of operations is $$$0$$$, $$$1$$$, or $$$2$$$. We have $$$3$$$ cases:

1. No operations are needed if $$$s$$$ already contains $$$k$$$ characters $$$\texttt{B}$$$.

2. Else, we can use brute force to check if changing some prefix leads to $$$s$$$ having $$$k$$$ $$$\texttt{B}$$$s. If we find such a prefix, we print it as the answer, and use only one operation. There are $$$O(n)$$$ possibilities. implementing them takes $$$O(n)$$$ or $$$O(n^2)$$$ time.

3. Else, we use the two operations described in the hint section.

A fun fact is that only one operation is enough. Can you prove it?

If at some point Milena divides $$$a_i$$$ on $$$x$$$ and $$$y$$$, that will not affect the subarray right from $$$a_i$$$ (by dividing some element, it can only get smaller). That means we can try greedy from right to left.

Let's assume we have sorted subarray $$$[a_{i+1}, \dots, a_n]$$$, and now we are operating on element $$$a_i$$$. After every operation the number of elements increases by 1, so we need $$$x-1$$$ operations to divide some element on $$$x$$$ integers.

...

...