Peter is studying mathematics and he just discovered prime numbers, he also likes programming a lot, so he plans spent this weekend creating (and then coding) a new method to encrypt text messages.... His main objective is to hide the messages he is receiving from his girlfriend to the curious eyes of his little brother....

His idea is the following: the program will receive a text message to encript (with a maximun length of 10000 characters). Then, the program will generate the output message where the input text will be hidden.

The message is encripted, storing it -after reversed-, letter by letter, in the positions indexed by the n first prime numbers (where n is the length of the message).

The remaining positions will be filled in this way:

• The first letter in the input message wil be copied once in the first position unused at the output (from left to right).

• The second letter in the input message will be copied twice starting from the following unused position at the output.

• ….

• The ith letter in the input will be copied i times starting from the next unused position.....(maybe the last letter used in the filling process be used lesser times)

• The blanks at the input message won't be used to this filling process (only letters and digits).

• The filling process will finish when all the unused positions before the right most prime position be taken.

Let's say this idea isn't brilliant..., but his little brother isn't very smart, so Peter is confident will be enough.

Input

The input contains several test cases. The first line of a test case contains one integer N indicating the number of text messages to be encripted (1 ≤ N ≤ 50).

The following N lines contain one input message per line. The maximun length per message is 10000 characters.

You can assume there aren't spaces at the beginning or the end of the message, and there aren't two consecutive spaces.

Output

For each text message in the input, the output will contain one line with the text message encripted.

Sample input

2

RUMBO A ACM

WE WILL BE IN TOP 3

Sample output

RMCUAU MMMAB BBBOOBOOOMOAAAAUAR

W3 EPEOWWWTI IIINLILLL LLLLLELBLBBBB BBBLELEEEIEEEEIWIIIII IEIINNNW