예쁜 문자열

공백이 없는 문자열 $S$를 여러 줄로 나누어 출력하려 한다. 출력하는 줄의 수를 $k$라 하고, $i$번째 줄의 문자 수를 $a_i$라 하자. 어떤 양의 정수 $n$에 대해 $a_1=1$이고 $a_i=a_{i-1}+n$ ($2\leq i\leq k$)이어야 한다.

문자열 $S$의 문자를 순서대로 빠짐없이 사용하여 각 줄을 만든다. 가능한 방법이 없다면 $0$을 출력한다. 가능한 방법이 여러 개라면 줄 수 $k$가 가장 큰 방법을 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 케이스마다 조건을 만족하도록 나눈 문자열을 각 줄에 하나씩 출력한다. 불가능하면 $0$만 한 줄에 출력한다. 별도의 줄 수나 $n$은 출력하지 않는다.

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