题目描述

FJ 的奶牛又来餐厅就餐了（不是奥利给哟），现在 FJ 要求奶牛们分 \(3\) 批就餐：所有第 \(3\) 批就餐的奶牛，中间的位置就归第 \(2\) 批的奶牛。第 \(i\) 头奶牛有一张标明她用餐批次 \(D_i\) 的卡片，FJ 仍然用原排在队尾，第 \(1\) 批就餐的奶牛则占据队首来的方法操作： 奶牛们不动，他沿着队伍从头到尾走一遍，把那些他认为排错队的奶牛卡片上的编号改掉，最终得到一个他想要的每个组中的奶牛都站在一起的队列，例如 \(111222333\) 或 \(112222233\)，甚至于允许出现 \(333222111\)，此时所有奶牛整个向后转即可。有的时候，FJ 会把整个队列弄得只有 \(1\) 组奶牛（比方说，\(111\) 或 \(222\) 或 \(333\)）。他想知道，如果他想达到目的，那么他最少得改多少头奶牛卡片上的编号。所有奶牛在 FJ 改卡片编号的时候，都不会挪位置。

格式

输入格式

第一行为正整数 \(t(≤5)\)，表示测试数据组数；每组数据的第一行为正整数 \(n(≤30000)\)，表示奶牛个数；接下来一行，为 \(n\) 个正整数 \(D_i\)(\(D_i=1,2\) 或 \(3\))，分别表示为每头奶牛的用餐批次。

输出格式

对于每组数据，输出 FJ 最少要改编号的个数。

样例1

样例输入1

2
10
2 3 2 1 2 1 2 2 2 1
20
2 2 3 2 3 2 3 3 2 1 3 2 1 3 3 1 1 2 2 1

样例输出1

3
10

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T4\)

文件IO

freopen("dining.in","r",stdin);
freopen("dining.out","w",stdout);