회문 수열 만들기

회문 수열은 앞에서 읽어도 뒤에서 읽어도 같은 수열, 즉 {a1, a2, a3, ..., a3, a2, a1} 꼴의 수열이다. 예를 들어 {78, 91, 78}, {100}, {10, 20, 20, 10}, {5, 5, 5, 5}는 회문 수열이다. 하지만 {1, 2, 3, 1}과 {10, 20}은 회문 수열이 아니다.

정수 수열이 주어진다. 삽입을 여러 번 수행해서 이 수열을 회문 수열로 바꾸려고 한다. {1, 2, 3, 1}은 네 번째 위치에 2를 삽입하면 {1, 2, 3, 2, 1}이 되어 회문 수열이 된다. {10, 20}은 첫 번째 위치에 20을 삽입하거나 마지막 위치에 10을 삽입하면 회문 수열이 된다.

주어진 정수 수열을 회문 수열로 만드는 데 필요한 최소 삽입 횟수를 구하라. 결과(삽입 횟수)는 항상 100보다 작다고 보장된다.

첫 줄에는 검사할 정수 수열의 개수 n이 양의 정수로 주어진다. 이후 2n개의 줄에 수열이 하나당 두 줄씩 주어진다. 각 수열의 첫 줄에는 수열의 크기 s (1 ≤ s ≤ 10,000)가 주어지고, 둘째 줄에는 공백 한 칸으로 구분된 s개의 정수가 주어진다. 수열의 각 정수는 1 이상 50 이하이다.

각 수열에 대해 먼저 "Sequence #i: "를 출력한다. 여기서 i는 1부터 시작하는 수열 번호이다. 이어서 수열을 회문 수열로 만드는 데 필요한 최소 삽입 횟수를 정수 하나로 출력한다. 각 테스트 케이스의 출력 뒤에는 빈 줄을 하나 남긴다. 출력 형식은 예제 출력을 따른다.