Problem Statement:
Years ago, when kings send messages to their allies; the most important thing is to deny any person to understand the content of the message if he can get it. They used a sophisticated method to encrypt their messages. After writing the message they put it in a square grid, and then they traverse the grid by its diagonals one by one and reformate the message. If the message length is smaller than the grid?s cell count; fill the remaining with ?*?, if longer; ignore the rest of the message.


The message is ?Tomorrow, we will invade Sparta!? and the grid dimensions is 6

Then the letter should be printed in the following order:

When the messages got too long, the process became too boring, so they need a computer program to do this job.
Then the message will be:

Toomw o,wir in rwlvSaelap! da*er*t**

Input Format:
The first line is the number of test cases, there will be at most 100 test cases. Each test case is presented on one line that starts with the grid?s size (Max size is 19), a space, then the message; the message may contains any printable character, its length is at least one character.

Output Format:
For each test case output the encrypted message.

Sample Input:
2 6 Tomorrow, we will invade Sparta! 2 Hello

Sample Output:
Toomw o,wir in rwlvSaelap! da*er*t** Hell

Added by: feras_kassar
Added at: 2014-05-19 20:19:46 UTC
Time Limit: 2 seconds
Partial score: No
Source:Tishreen-CPC 2014