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:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def min_insert(s):
	if len(s) == 1 or len(s) == 0:
		return 0
	return min_insert(s[1:-1]) if s[0] == s[-1] else 1 + min(min_insert(s[:-1]), min_insert(s[1:]))

T = input()
for t in xrange(T):
	N = input()
	s = raw_input()
	print min_insert(s)