说明

gsy 最近玩了一个很特别的消消乐，这个消消乐的规则跟一般的消消乐不太一样。

这个消消乐中共有 n 个方块排列成一排，每个方块均有一个标号，分别为 a_1,a_2,a_3...a_n。

游戏一开始需要设置其中一种方块为 "消除块"，这些 "消除块" 是不可以被消除的，而当选择了消除块后，游戏会自动在这 n 个方块序列的前后各添加一个 "消除块"。

而 gsy 可以进行的操作就是，选择两个 "消除块"，这两个块之间的所有方块将被删除。

但是注意，若选择的两个消除块之间存在消除块，则此次消除将会失败。

当所有非消除块被消除完后，游戏结束，而每一次操作会降低 1 分得分，即操作次数越少，得分越高。

例如有 5 个方块 [1,2,3,2,1]，gsy 可以选择的游戏流程如下：

1. 选择 3 为 "消除块"，游戏自动在首尾各添加一个 "消除块"，方块序列变为 [3,1,2,3,2,1,3] 
2. 选择 a_0 和 a_3 两个消除块进行消除，方块序列变为 [3,3,2,1,3]
3. 继续选择 a_1 和 a_4 两个消除块进行消除，方块序列变为 [3,3,3]，游戏结束

在这个游戏过程中，gsy 总共进行了 2 次操作，但是显然有操作次数更少的方法:

1. 选择 1 为 "消除块"，游戏自动在首尾各添加一个 "消除块"，方块序列变为 [1,1,2,3,2,1,1] 
2. 选择 a_1 和 a_5 两个消除块进行消除，方块序列变为 [1,1,1,1]，游戏结束

这样 gsy 只需要 1 次操作即可

现在 gsy 为了偷懒，她想知道每一轮游戏中，选择哪种 "消除块" 可以使得操作次数最少。

输入格式

第一行包含一个正整数 T 表示共有多少轮游戏。

对于每轮游戏输入包含两行：
1. 第一行包含一个正整数 n 表示这轮共有多少个方块
2. 第二行包含 n 个整数 a_1,a_2,a_3...a_n 分别表示每个方块的编号

对于 30% 的数据，T <= 10, 2 <= n <= 10^2

对于 100% 的数据，T <= 1000, 2 <= n <= 10^5 , 1 <= a_i <= n ,\sum{n} <= 2 * 10^5

输出格式

对于每一轮游戏输出包含两个整数，分别表示选择的 "消除块" 的编号和最少需要的操作次数。

若存在多种 "消除块" 方案可以使得操作次数最少，那么选择最小的 "消除块" 编号。

样例

3
4
2 2 2 2
5
1 2 3 4 5
11
2 1 2 3 2 1 2 3 1 2 2

2 0
1 1
3 3