D :: Davood Inchi Code

Time Limit: 2 Seconds    Memory Limit: 65536 KB

Bahman loves Dan Brown’s books. He has read all of them and now he thinks he can come up with a nice story himself. This is part of his drafts for the book:

“... Rambod Langaan found the dead body on the floor. He couldn’t see clearly in that dark, but he could definitely recognize the smell. The body should have been there for a few days. Holding his breath, he got closer and reached the bag. It was wet.
As soon as he got out of the tunnel, he filled his lungs with fresh air. Now he could think more clearly. The bag was wet; not from the water in the tunnel, but from the blood. His body shivered. He had no choice. Without any further thoughts, he opened the bag and immediately found what he was looking for: an old piece of parchment. He couldn’t believe what he was seeing. Those were the exact same notes that Davood Inchi wrote more than a thousand years ago. They were the rules of their underground society, called Folan, but they were what all people thought. Rambod knew more than those. This was actually an encrypted message for those who were really a part of Folan, the location of their secret gatherings. Taking out the characters at Fibonacci indices and putting them together would reveal the message. That was easy for Rambod. He wrote the first, second, third, fifth and eighth characters out and wrote them on his hand; “Thefsl” was what he had on his hand! What could that possibly mean? The sentence on the parchment started with “The first rule”. “This cannot be right” he thought. He tried more letters but suddenly he reached the end of the parchment. But there were not enough letters. So he continued backwards through the text. He reached the beginning of the text, reversed the direction and continued picking toward the end of the text. He couldn’t do this forever. He had no time. There was someone out there killing people... ”

Forget about what Bahman was doing! Just help Rambod Langaan to find the hidden message.
And don’t try to find the secret place! You can’t!
What you should do is to pick characters with Fibonacci steps which are 1, 1, 2, 3, ... (so pick the first, second, third, fifth, eighth and ... characters). If you reach one of the end-points in the string, then reverse your direction and continue. Moreover, if you where to pick a ’-’ character, reset your Fibonacci sequence to 1, 1, 2, 3, ... . Continue until you have enough characters. 

 

Input

The input contains several test cases.
In the first line of input comes T (0 < T < 64), the number of test cases.
Each test case consists of two lines, a line with a number K (0 < K < 32), denoting the number of characters Rambod needs to find, and a line with a string with length l (1 ≤ l ≤ 1024), the text on the parchment. The string includes at least one character other than ’-’.

Output

For each test case write the hidden message on a separate line.

Sample Input

2
6
Hello World
15
12th-Iran-Internet-ACM-ICPC-2014-Final

Sample Output

Heloor
12tIraIntrtICP2
Submit

Source: 12th Iran Nationwide Internet Contest - Final