Pretty String

You want to split a string $S$ with no whitespace into several lines. Let $k$ be the number of printed lines and $a_i$ the number of characters on line $i$. For some positive integer $n$, we must have $a_1=1$ and $a_i=a_{i-1}+n$ for $2\leq i\leq k$.

Use every character of $S$ exactly once and preserve their order. If this is impossible, print $0$. If several valid splits exist, print one with the largest number of lines $k$.

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

For each case, print the pieces of a valid split, one piece per line. If no split exists, print only $0$ on one line. Do not print the number of lines or $n$ separately.

• $1\leq T\leq100\,000$.
• $1\leq |S|\leq10^6$.