11716 - Digital Fortress

本題給定一個加密字串，請你將它解密，例如下列字串： WECGEWHYAAIORTNU 將它解密後得到： WEAREWATCHINGYOU 解密的原理如下：對於一個密文長度為平方數(1, 4, 9, 16, 25, 36...)的字串，例如本例密文長度16，為4的平方，將密文以"列順序"的方式來填入一個n*n的格子中(本例n=4)，也就是將前n個字母填入第一列，再將之後的n個字母填入第二列，以此類推…如下所示： W  E  C  G E  W  H  Y A  A   I   O R   T  N  U 再將上面方陣中的元素以"行順序"的方式讀出(第一行由上往下，再取第二行由上往下…)，得到解密的資訊： WEAREWATCHINGYOU
Input
輸入的第一列為整數T，表示測試資料的組數，每組測試資料一列表示加密的密文，且皆為大寫字母或是空白字元，字串長度不超過10,000。
Output
請輸出每筆資料解密後的明文，若長度非任何數的平方數，則請輸出INVALID。
Sample Input	Output for Sample Input
3 WECGEWHYAAIORTNU DAVINCICODE DTFRIAOEGLRSI TS	WEAREWATCHINGYOU INVALID DIGITAL FORTRESS
原文出處