Problem: 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

SAMPLE INPUT
2
5
nitin
7
aabbaab

SAMPLE OUTPUT
0
1

Solution (in PYTHON):

Solution:
#finding the longest common subsequence of s and rev(s)
def longestSeq(s):
    dp = [[0 for i in xrange(len(s)+1)] for i in xrange(len(s)+1)]
    rev = s[::-1]
    for i in xrange(len(s)+1):
        for j in xrange(len(rev)+1):
            if(i==0 or j==0):
                dp[i][j] = 0
            elif(s[i-1]==rev[j-1]):
                dp[i][j] = dp[i-1][j-1] +1
            else:
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
    return dp[len(s)][len(s)]
for _ in xrange(input()):
    n=int(input())
    x=raw_input()
    print len(x)-longestSeq(x)