Minimum Operations to Convert to Palindrome

You are given a string S of length N consisting of lowercase English letters. Your task is to determine the minimum number of operations required to convert S into a palindrome. In one operation, you can insert a character at any position, delete a character, or replace a character.

Note: The operations are defined such that the transformed string must read the same forwards and backwards.

The required answer is guaranteed to exist and can be computed using dynamic programming. The recurrence relation can be described in LaTeX as follows:

\[ \text{dp}[i][j] = \begin{cases} 0, & \text{if } i \geq j, \ \text{dp}[i+1][j-1], & \text{if } S[i] = S[j], \ \min(\text{dp}[i+1][j], \text{dp}[i][j-1]) + 1, & \text{if } S[i] \neq S[j]. \end{cases} \]

inputFormat

The first line of the input contains an integer T (1 ≤ T ≤ 50) representing the number of test cases. Each test case consists of two inputs in a single line:

• An integer N (1 ≤ N ≤ 1000) representing the length of the string.
• A string S of length N containing only lowercase English letters.

Inputs for each test case are space separated. All test cases are given consecutively.

outputFormat

For each test case, output a single line containing a single integer: the minimum number of operations required to convert the given string into a palindrome.

## sample

2
3 abc
4 abca

2
1

</p>