# [Solution] Make Palindrome 2 solution codechef

Make Palindrome 2 solution codechef – You are given a binary string SS of length NN. You want to obtain a palindrome from SS by applying the following operation at most N2⌊N2⌋ times:

• Choose an index i(1i|S|)i(1≤i≤|S|), delete the character SiSi from SS and concatenate the remaining parts of the string. Here |S||S| denotes the current length of string SS.

## [Solution] Make Palindrome 2 solution codechef

For example, if S=S= 11010, then applying the operation on index i=2i=2 makes S=S= 1010.

Note that after each operation, the length of the string SS decreases by one.

Find any palindrome you can obtain after the operations. It can be proved that it is always possible to obtain a palindrome from SS under the given constraints.

Here, N2⌊N2⌋ denotes floor division of the integer NN by 22. For example, 52=2⌊52⌋=282=4⌊82⌋=4. A binary string is a string that consists of only the characters 0 and 1.

### Input Format

• The first line of input contains an integer TT, denoting the number of test cases. The TT test cases then follow:
• The first line of each test case contains an integer NN, denoting the length of the binary string SS.
• The second line of each test case contains the binary string SS.

## [Solution] Make Palindrome 2 solution codechef

For each test case, print on a separate line any palindromic string that can be obtained from SS by applying the given operation at most N2⌊N2⌋ times.

### Constraints

• 1T10001≤T≤1000
• 1N1001≤N≤100
• SS contains only the characters 0 and 1.

### Sample Input 1

4
3
101
3
001
4
1011
6
010011


## [Solution] Make Palindrome 2 solution codechef

101
00
111
1001


### Explanation

Test case 11: The given string is already a palindrome.

Test case 22: Applying the operation on index i=3i=3 makes S=S= 00 which is a palindrome.

Test case 33: Applying the operation on index i=2i=2 makes S=S= 111 which is a palindrome.

Test case 44: Applying the operation on index i=1i=1 makes S=S= 10011. Then applying the operation on index i=5i=5 makes S=S= 1001 which is a palindrome.