小青鱼被神秘力量传送到了重（zhòng）庆市的一个陌生的街头。这里有一位智者，似乎知道很多东西，但你只有在一个古老的游戏中打败他，他才会认真和你对话。为了从智者那里知道些什么，小青鱼决定接受智者的游戏挑战。

这个游戏的规则是这样的：你面前有一个长度为 $n$ 的序列，序列由 $n$ 个整数构成，且保证 $n$ 是奇数。

两位玩家，小青鱼和空间的使者，将轮流进行操作。在每一轮中，玩家可以从序列中选择任意两个相邻的元素并将它们删除。删除后，这两个元素两侧的剩余序列将会自动合并。这样的操作将持续进行，直到序列中只剩下一个元素。

在这场游戏中，小青鱼是先手。他的目标是在游戏结束时让剩下的那个整数尽可能的大，而智者则希望让最后剩下的整数尽可能小。

面对如此高难度的挑战，小青鱼一下子就否定了几个过于简单的策略。然而究竟应该如何让最后剩下的整数尽可能大呢？小青鱼需要你的帮助。

请你帮助小青鱼找到最优的博弈策略，并输出当小青鱼以该策略进行博弈，且智者也以自己的最优策略进行对抗时，最后剩下的整数会是多少。

看着焦头烂额的你和小青鱼，智者提醒道：那些你不要的，那些被你忽视的，往往才是最重要的。

输入格式

第一行，一个整数 $T$，表示有 $T$ 组数据。

每组数据第一行一个奇数 $n$，表示序列长度。

第二行 $n$ 个整数 $a_1,\dots ,a_n$。

输出格式

对于每组数据，输出一行一个整数表示答案。

样例一

input

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

output

3
3
2
2

explanation

第一组数据，先手删掉 $1,2$，序列变为 $[3,4,5]$，然后后手删掉 $4,5$。

第二组数据，先手删掉 $1,2$。

第三组数据，先手删掉 $1,3$。

第四组数据，先手删掉 $1,1$，序列变为 $[3,3,2]$，然后后手删掉 $3,3$。

样例二/三

见附件下载。

数据范围

对于每个测试点：$T\ge 1$，$1\le n\le {10}^6$，$1\le a_i\le n$。每个测试点内的所有数据的 $n$ 之和（记为 $\sum n$）不超过 ${10}^6$。

时间限制：$1\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$