팬케이크 timer 2초 memory 1024MB

비타로는 팬케이크점에서 일하고 있다.

이 가게에서 가장 인기있는 메뉴는 N 장의 팬케이크가 쌓인 팬케이크 타워이다. 가게에서 만들어진 팬케이크에는 3종류의 맛이 있으며, 각각 A, B, C라고 부르기로 한다.

여기서, 팬케이크의 배열 방법이 다음 조건을 만족시키는 팬케이크 타워를 좋은 팬케이크 타워라고 부른다.

• 모든 맛 A의 팬케이크와 맛 B의 팬케이크 세트에서 맛 A의 팬케이크는 맛 B의 팬케이크 위에 있다.

• 모든 맛 A의 팬케이크와 맛 C의 팬케이크 세트에서 맛 A의 팬케이크는 맛 C의 팬케이크 위에 있다.

• 모든 맛 B 팬케이크와 맛 C 팬케이크 세트에서 맛 B 팬케이크는 맛 C 팬케이크 위에 있다.

예를 들어, 팬케이크의 맛이 각각 위에서 순서대로 AABBBC, ACC, BBBB가 되어 있는 팬케이크 타워는 모두 좋은 팬케이크 타워이지만, AABABCC, CA가 되어 있는 팬케이크 타워는 모두 좋은 팬케이크 타워가 아니다.

비타로는 팬케이크 타워에 대해 다음 작업을 수행 할 수 있습니다.

• 조작 k (2 ≤ k ≤ N) : 위에서 k 번째 팬케이크의 아래쪽에 뒤집개를 넣고 거기에서 위의 팬케이크를 뒤집는다. 즉, 위에서 k 장의 팬케이크의 배열 방법을 반전시킨다.

예를 들어, 팬케이크의 맛이 위에서부터 순서대로 ABCB가 되어 있는 팬케이크 타워에 조작 2, 조작 3, 조작 4를 각각 행한 경우, 팬케이크의 배열 방법은 BACB, CBAB, BCBA가 된다.

이제 Q 접시의 팬케이크 타워가 있고, i 접시 (1 ≤ i ≤ Q)의 팬케이크 타워는 팬케이크의 맛이 위에서부터 순서대로 S_{i_1}, S_i{_2}, …, S_{i_N}이다. 비타로는 각각의 팬케이크 타워에 대해 가능한 한 적은 횟수의 조작으로 좋은 팬케이크 타워로 만들고 싶다.

Q 접시의 팬케이크 타워의 배열 방법에 대한 정보가 주어지므로, 각각의 팬케이크 타워에 대해, 좋은 팬케이크 타워로 하는데 필요한 조작의 횟수의 최솟값을 구하는 프로그램을 작성하라.