비밀 메시지

잭과 질은 도청을 걱정하지 않고 대화하려고 암호화 방법을 하나 만들었다. 방법은 다음과 같다.

원본 메시지의 길이를 $L$이라 하고, $L$ 이상인 제곱수 중 가장 작은 값을 $M$이라 하자. 메시지 뒤에 별표 *를 $M - L$개 붙여 길이가 $M$인 메시지를 만든다. 이 메시지를 $K \times K$ 표에 행 우선 순서로 채운다. 여기서 $K^2 = M$이다. 행 우선 순서란 위쪽 행부터 차례로 채우고, 각 행에서는 왼쪽 칸부터 채우는 것을 말한다. 표를 시계 방향으로 90도 회전한다. 회전한 표를 행 우선 순서로 읽으면서 별표를 뺀 결과가 암호문이다.

예를 들어 원본 메시지가 iloveyouJack이면 길이가 $L = 12$이므로, 별표를 붙인 메시지는 iloveyouJack****이고 길이는 $M = 16$이다. 회전 전과 회전 후의 표는 다음과 같다.

회전 전         회전 후
i l o v         * J e i
e y o u         * a y l
J a c k         * c o o
* * * *         * k u v

별표를 빼고 읽으면 암호문은 Jeiaylcookuv이다.

첫 줄에 원본 메시지의 개수 $N$이 주어진다 ($1 \le N \le 100$). 다음 $N$개 줄에는 암호화할 메시지가 한 줄에 하나씩 주어진다. 메시지는 알파벳 소문자와 대문자로만 이루어지고, 길이 $L$은 $1 \le L \le 10000$을 만족한다.

원본 메시지마다 암호문을 한 줄에 하나씩 출력한다.