A Tommy piacciono due cose: l'urbanistica e gli espressi macchiati. Le sue giornate sono piene di impegni, lavora ventiquattr'ore su ventiquattro e ha a malapena un minuto per fermarsi a fare due chiacchiere -- ma un uomo ha le sue priorità, e il caffè è molto importante per lui. Così, quando gli viene affidato l'incarico di progettare una città completamente nuova, coglie l'occasione: assicurarsi esattamente un macchiato lungo il tragitto verso il lavoro, ogni singola mattina, senza stress.

La città è una griglia $n \times n$. La casa di Tommy si trova nell'angolo in alto a sinistra e il suo posto di lavoro nell'angolo in basso a destra. È sempre di fretta, quindi nel tragitto a piedi da casa al lavoro si sposta solo verso destra e verso il basso.

Vuole progettare la città in modo che valgano entrambe le seguenti condizioni:

• Ogni casella della griglia non ha alcuna caffetteria oppure ha esattamente una caffetteria. La casa e il posto di lavoro di Tommy non possono avere caffetterie.

• Non importa quale percorso scelga Tommy nella griglia, il suo cammino lo porta ad attraversare esattamente una casella che ha una caffetteria.

Un macchiato ogni mattina -- mai nessuno, perché ne ha bisogno, e mai due, perché chi ha il tempo? Aiutalo a progettare la città rispettando i suoi vincoli!

Input

La prima riga di input contiene un singolo intero $t$ $(1 \le t \le 49)$, che indica il numero di casi di test.

Seguono le descrizioni di $t$ casi di test. Ciascun caso di test è composto da una singola riga con un singolo intero $n$ $(2 \le n \le 50)$, che rappresenta la dimensione della città che Tommy sta progettando.

Output

Per ciascun caso di test, stampa una griglia $n \times n$. Ogni carattere deve essere . per indicare una casella senza caffetteria oppure C per indicare una casella con una caffetteria.

Se esistono più piani urbanistici validi, uno qualsiasi verrà accettato. Si può dimostrare che è sempre possibile costruire un piano urbanistico valido.

Esempio

Input 1

2
6
7

Output 1

.....C
....C.
...C..
..C...
.C....
C.....
.......
.......
.......
.......
......C
.....C.
....C..