teddy online judge

100. Ácido RiboNucléico

Limite de tiempo : 3 seg.   Total runs : 142  Aceptados : 72

Zymobacter celayens es el nombre de una curiosa bacteria descubierta por el Instituto de Tomografía Computarizada (ITC) utiliza un método único para asegurar que su material genético siempre esté mutando: justo antes de la creación de proteínas mediante el mRNA (ácido ribonucléico mensajero), acomoda las bases de la cadena de mRNA en una matriz cuadrangular en el orden de las filas, y luego recupera la cadena por las columnas. Esto es, si tuviéramos una cadena con los números del 1 al 9, se acomodarían así:

Y se leería la secuencia como 147258369. Tu labor es, a partir de la secuencia de mRNA que leíste, encontrar la secuencia original.

Entrada

La primer línea de la entrada contiene un entero N_c (1 ≤ N_c ≤ 100), que contiene el número de casos de prueba. Cada caso de prueba contiene un entero N (1 ≤ N ≤ 100,000), la longitud de la cadena leída. La siguiente línea contiene una cadena de N caracteres, representando las bases nitrogenadas. Cada uno de los caracteres es uno de 'G', 'C', 'A' o 'U'. Se garantiza que todas las cadenas tienen una longitud tal que pueden ponerse todos sus caracteres en una matriz cuadrada sin que falten o sobren espacios.

Salida

Para cada caso de prueba, imprime una línea con el número del caso, seguido de la secuencia original de bases nitrogenadas que componí el mRNA.

Entrada/Salida de ejemplo

3
1
G
4
GGCG
9
GUUGUGUCG

Caso 1: G
Caso 2: GCGG
Caso 3: GGUUUCUGG