C. There are many books and books
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

志愿时长 400h！

你在图书馆担任图书管理员，在书架上有一些书，它们的编号为 $$$1$$$ 或 $$$2$$$，你需要改变书的顺序，使得编号相同的书被放在一起。 在你的每次操作中，你可以把一本书移动到书架的开头或者把一本书移动到书架的末尾，其它书的相对位置不会发生改变。 请问为了使得书架上编号相同的书被放在一起，你需要进行最少的移动次数为多少。

Input

第一行，一个整数 $$$t(1\le t\le 10^4)$$$，代表数据组数。

对于每组数据： 第一行，一个整数 $$$n(1\le n \le 2·10^5)$$$，代表书的数量。 第二行，$$$n$$$ 个整数 $$$a(1\le a\le2)$$$，代表每本书的编号。

保证同一测试点内的 $$$\sum n \le 2·10^5$$$

Output

对于每组数据，输出一个整数代表为了使得书架上编号相同的书被放在一起，你需要进行最少的移动次数的数量。

Example
Input
5
4
1 1 2 2
4
2 1 1 2
5
1 2 1 2 2
7
1 2 1 1 1 2 1
1
2
Output
0
1
1
2
0