Minimum Insertions to Form a Palindrome

You are given a sequence of integers, and your task is to compute the minimum number of insertions required to transform the sequence into a palindrome. A palindrome is a sequence that reads the same backward as forward.

This can be achieved by finding the longest palindromic subsequence (LPS) of the given sequence. If the length of the sequence is \(M\) and the length of its LPS is \(L\), then the minimum number of insertions needed is \(M - L\). Formally, you need to compute:

[ \text{Minimum Operations} = M - LPS(B) ]

Input Format: The first line contains an integer \(T\), the number of test cases. Each test case consists of two lines. The first line of each test case contains an integer \(M\) (the length of the sequence), and the second line contains \(M\) space-separated integers representing the sequence.

Output Format: For each test case, output a single integer denoting the minimum number of insertions required to make the sequence a palindrome.

inputFormat

The first line of input contains an integer \(T\) representing the number of test cases. For each test case, the first line contains an integer \(M\) which is the length of the sequence. The second line contains \(M\) space-separated integers, representing the sequence \(B\).

outputFormat

For each test case, output a single integer on a new line which is the minimum number of insertions required to transform the given sequence into a palindrome.

## sample

3
7
1 2 3 4 3 2 1
5
1 2 3 1 2
3
1 2 3

0
2
2

</p>