비밀 편지

선영이는 남자친구에게 보낼 연애 편지를 썼다. 편지가 다른 사람에게 읽히지 않도록, 선영이는 다음과 같은 방법으로 편지를 암호화한다.

1. 편지 내용을 한 변의 길이가 같은 정사각형 격자에 왼쪽 위부터 한 글자씩, 행 방향(왼쪽에서 오른쪽, 위에서 아래)으로 채워 넣는다.
2. 이 정사각형을 시계 방향으로 90도 회전시킨다.
3. 회전한 정사각형을 다시 첫 번째 행부터 마지막 행까지 행 방향으로 읽어 한 줄로 이어 붙인다. 이렇게 만들어진 문자열이 암호문이다.

선영이는 편지에 띄어쓰기를 넣지 않으므로, 편지의 길이는 항상 제곱수이다.

예를 들어 원래 편지가 RosesAreRedVioletsAreBlue(길이 25, 즉 5×5 정사각형)이면, 암호화한 편지는 eedARBtVrolsiesuAoReerles가 된다.

암호화된 편지가 주어졌을 때, 원래 편지의 내용을 복원하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $T$는 최대 $100$이다.

이후 $T$개의 줄에 각각 하나의 암호화된 편지가 주어진다. 각 편지는 알파벳 대문자와 소문자로만 이루어져 있으며, 길이는 $1$ 이상 $10000$ 이하이고 항상 제곱수이다.

각 테스트 케이스마다 복원한 원래 편지를 한 줄에 출력한다.