Palindrome Maker

A palindromic integer sequence is a sequence that reads the same forwards and backwards, that is, a sequence of the form {a1, a2, a3, ..., a3, a2, a1}. Some examples are {78, 91, 78}, {100}, {10, 20, 20, 10}, and {5, 5, 5, 5}. But {1, 2, 3, 1} and {10, 20} are not palindromic sequences.

You are given an integer sequence. You want to convert it into a palindromic integer sequence by a series of insertions. You can convert {1, 2, 3, 1} into a palindromic sequence by inserting a 2 at the fourth position, which gives {1, 2, 3, 2, 1}. You can convert {10, 20} into a palindromic sequence by inserting 20 at the first position or by inserting 10 at the last position.

Given an integer sequence, find the minimum number of insertions required to convert it into a palindromic sequence. It is guaranteed that the result (the number of insertions) is always less than 100.

The first line contains a positive integer n, the number of integer sequences to check. The sequences are on the following 2n lines, two lines per sequence. The first line of each sequence contains s (1 ≤ s ≤ 10,000), the size of the sequence. The second line contains s integers separated by a single space, which form the sequence. The integers in a sequence are between 1 and 50, inclusive.

For each sequence, first output "Sequence #i: ", where i is the sequence number starting from 1. Then output a single integer, the minimum number of insertions required to convert the sequence into a palindromic sequence. Leave a blank line after the output for each test case. Follow the format shown in the sample output.