You are given a string of characters, or numbers. Find the minimum number of characters to be inserted into the string in order to obtain a palindrome. A palindrome is a word, phrase, number, or other sequence of symbols or elements that reads the same forward or reversed.
For example, the string abcbd can be transformed into a palindrome ("dabcbad" or "adbcbda"). However, inserting fewer than 2 characters will not produce a palindrome.
Input Format:
First line contains test cases and second line contains an integer 'n' specifying the length of the string, where 3<=n<=20 Second line contains a string of length n.
Note:
Upper-case and lower-case characters are considered as different. Elements of the string are either English alphabets or numerals.
Output Format:
One line containing the minimum number of insertions required to make the string a palindrome