稷下学宫（admission）

时空限制

• 时间限制：1s
• 内存限制：512M
• 测试数据共 20 组

题目背景

稷下学宫是战国时期的高等学府，是世界上最早的官办高等学府。《史记·田敬仲完世家》中记载：

“宣王喜文学游说之士，自如邹衍、淳于髡、田骈、接子、慎到、环渊之徒七十六人，皆次列第为上大夫，不治而议论，是以稷下学士复盛，且数百千人。”

当时齐国的国君广开言路，重视人才，选贤任能，因此建立稷下学宫。但是由于名声太大，每天赶往稷下学宫想要发表自己的学术见解的学子都在门口大排长龙，初审官根本来不及听每一个人的策论。

题目描述

你作为稷下学宫的新晋门卫，决定要为长官出谋划策，既可以让更多国别的学子都能够有机会阐述自己的观点，也能让长官少加班。根据经验，来自同一个国别的学子，习俗与观点会比较类似：比如鲁国乃姬姓诸侯是周礼的保存者和实施者；楚人多信巫鬼，重祭祀；夜郎国人没见过世面普遍自大等等。

你想到了一个主意：学子们按照报道的先后顺序列队，依次把自己的姓名和国别刻在竹简上，交给门卫；门卫根据国别代号进行筛选。要使稷下学宫吸纳多元化的声音，又要为长官剔除掉一些可能重复的观点，你正在谋划一套录取方案为长官完成一轮录取。

你已记录下 $n$ 名学子的列队情况，排在第 $i$ 位的学子的国别用正整数 $a_i$ 表示，相同数字代表相同的国别，不同数字代表不同的国别。根据列队顺序，你需要依次告知每个人是否被录取。淘汰的人离开列队，录取的人则留在队列中，原地不动。留下的人根据先后顺序会组成最终列队，其中任意连续的 3 人必须来自不同的国别。请问最终列队最多留下几人？

输入格式

每个测试点的第一行包含一个正整数 $T$ 表示有几组数据，$T \leq 10^5$。每组数据的描述如下：

• 每组数据第一行包含一个正整数 $n$，表示学子人数，$1 \leq n \leq 2 \times 10^5$。
• 每组数据第二行包含 $n$ 个正整数，由空格隔开，第 $i$ 个正整数为 $a_i$。

保证：$1 \leq a_i \leq 10^9$，$T$ 组数据的各个 $n$ 数值总和不超过 $2 \times 10^5$。

输出格式

输出共 $T$ 行，每行包含 1 个正整数，表示第 $i$ 组数据的答案。

样例 1 输入

3
5
1 2 1 2 1
7
1 2 3 2 1 2 3
8
1 10 10 1 1 100 100 1

样例 1 输出

2
6
4

样例 1 解释

• 第一组数据可以保留 (1, 2) 或 (2, 1)。
• 第二组数据可以保留 (1, 2, 3, 1, 2, 3)。
• 第三组数据可以保留 (1, 10, 100, 1)。

数据范围