【题目描述】

杰克和吉尔开发了一种特殊的加密方法，这样他们就可以在不担心窃听者的情况下自由的聊天。加密方法如下：设L为原始消息的长度，M为大于或等于L的最小平方数。在消息中添加（M-L）星号，给出长度为M的填充消息。使用填充消息填充大小为K×K的表，其中K×K=M。按行列顺序（从上到下一行，每行从左到右列）填写表格。将表格顺时针旋转90度。加密消息来自于从旋转表中按行列顺序读取的消息，省略任何星号。

例如，给定原始消息“iloveyouJack”，消息长度为L=12。因此，填充的消息是“iloveyouJack***”，长度M=16。以下是旋转前后的两张表。

然后我们读到了“Jeiaylcookuv”的秘密信息。

【输入】

第一行输入是原始消息的数量 N，1≤N≤100。以下N行的每一行都有一条要加密的消息。每条消息只包含字符a–z（小写和大写），长度为1≤L≤10000。

【输出】

对于每个原始消息，输出加密后消息。

【样本输入1】

2

iloveyoutooJill

TheContestisOver

【样本输出1】

iteiloylloooJuv

OsoTvtnheiterseC