Description

yangCA 和 Pear 正在游玩名为"开火车"的纸牌游戏。他们收集到写着 1 ~ n 的卡牌各两张，每个人持有n张卡牌。

游戏将会交替进行，yangCA 为先手。每次行动时，当前玩家都需要从自己的牌中选出一张并放置在牌堆顶部。如果此时牌堆出现了两张数字一样的牌，则当前玩家获得 1 分，并且将两张牌与之间的所有牌取出，放在弃牌区。

yangCA 是这个游戏的新手，而 Pear 想要捉弄他。Pear 希望知道：对于 yangCA 的一种出牌顺序，如何最小化 yangCA 的分数?

Format

Input

本题包含多组测试数据，输入的第一行包含一个整数$T(1 \leq T \leq 10^5)$，代表测试数据组数。 对于每组测试数据： 输入的第一行包含一个整数 $n (1 \leq n \leq 10^5)$，代表卡牌的种类数。 接下来一行包含$n$个整数$a_1, a_2 …,a_n (1 \leq a_i \leq n)$，代表 yangCA 的出牌顺序。保证没有数字在 $a_i$ 中出现超过两次。 数据保证所有测试数据的 $n$ 总和不超过 $5 \times 10^5$。

Output

对每组测试数据: 输出一个整数，代表 yangCA 的最小得分。

Samples

2
3
1 2 3
5
1 4 5 1 4

0
1

Limitation

1s, 1024KiB for each test case.