Description
SunMoon likes spiral(漩渦). On the N*N’s space, he starts moving into the left top corner, (0,0), and walking right for totally N steps (including the first movement into (0,0)). He then walks down for N-1 steps, then walks left for N-2 steps and then walks up for N-3 steps… until no more steps are possible. When he walks across that space, he will draw '#' on the floor. The others that he doesn’t pass will be ‘ ‘. Please tell SunMoon what the resulting spiral(漩渦) looks like.
Input
There is a positive number T(1 <= T <= 1000). It means that there are T numbers.
In next T lines, each line contains a positive number N(1 <= N <= 5000)，which is the size of the space.
Output
Please show the resulting spiral(漩渦).
Note: The first step is to enter (0,0), and the second step is to enter (0,1)…and so on.