Cross-stitch Embroidery

Valya has been learning cross-stitch embroidery in her craft classes. To practice, she needs to create pattern templates shaped like a "cross," where the number of embroidered crosses along the diagonal corresponds to the pattern number. Your task is to help Valya prepare the necessary templates.

Input

The input begins with the number of templates, followed by the pattern numbers. Each of Valya's pattern numbers has a unique characteristic: they are always odd and do not exceed 80.

Output

For each pattern number provided in the input, generate the corresponding template. The templates should be output in the same order as the input, with each template separated by an empty line.

Examples