Once Saikat sir tried to open his safe, but later on he realised that he forgot his password (which is actually a binary string), so he calls Anuja ma’am for help. Anuja ma’am then sends an encrypted message as they both wanted to keep the password safe.

Lets say if the password is 

01100111

She encrypted this string by adding the adjacent bits of each bit to it (Characters off the left and right edges of the string are treated as zeroes), hence the new string will be 12211232

But on decryption Saikat sir realized that the decrypted string will not be unique and will lead to more than 1 binary strings. Being too much tired he asks you for help. 

Input

First line contains T (1 <= T <= 100) number of test cases.

Each test case consists of 2 lines, first line consists of N (1 <= N <= 1000) length of the string and second line contains the encrypted message.

Output

So for each test case first print “Test x:” where x is the test case number starting from 1. Then print all possible binary strings in lexicographic order.

If there is no string possible then print "Not Possible" without quotes.

Example

Input:
3
5
11111
3
122
7
2222222

Output:
Test 1:
01001
10010
Test 2:
011
Test 3:
Not Possible