题目背景

春节将至，阿春选购了一段超长的丝绸（总长可达 1e18 米）准备染色装饰。

题目描述

阿春先给丝绸的前 n 米完成了染色：第 i 米被染为颜色 ai​。接下来，她从第 n+1 米开始，按顺序给后续所有米（直到 1e18 米）染色，染色规则如下：

1.对于待染色的第 i 米（i>n），先统计当前已染色的所有丝绸段中出现过的不同颜色数量，记为 ci​； 2.将第 i 米染为颜色 ci​。

请你计算，丝绸的第 1e18 米最终被染成了什么颜色？

输入格式

本题包含多组测试数据。第一行输入一个整数 t（1≤t≤500），表示测试组数；每组测试数据的输入格式如下：

第一行输入一个整数 n（1≤n≤100），表示初始已染色的丝绸长度（米数）； 第二行输入 n 个整数 a1​,a2​,…,an​，依次表示第 1 到第 n 米丝绸的颜色。

输出格式

对于每组测试数据，输出一个整数，表示第 1e18 米丝绸的颜色。

样例

5
6
1 1 1 1 1 1
1
1000
5
8 10 15 20 25
8
2 5 2 4 1 2 5 3
6
40 4 1 95 8 40

1
1000
8
5
8

样例解释

第一个例子：初始 6 米均为颜色 1，已染色部分的不同颜色数始终为 1。因此从第 7 米开始，每一米都会被染为颜色 1，第 1e18 米自然也是 1。 第二个例子：初始 1 米为颜色 1000，已染色部分的不同颜色数为 1，因此第 2 米染为 1；此时不同颜色数变为 2，第 3 米染为 2；……；第 1001 米染为 1000，此时已染色部分的不同颜色数固定为 1000，后续所有米（包括第 1e18 米）都会染为 1000。