Description

开发一款伟大的独立游戏一直是畅畅的梦想，而今天畅畅终于迈出了他梦想的第一步：开发了一个$2048$小游戏。

但是，畅畅的$2048$小游戏并不完善，因为他的游戏地图只有一行，此外他的游戏规则也和正常的2048不一样。但是这并不影响畅畅的决心，不过好奇心旺盛的他现在有一个问题：

对于一个地图大小为$n*1$的$2048$游戏，能够合成的最大的数字是多少？现在畅畅想让你帮他回答这个问题。

题目说明：对于给出的一行n个正整数，玩家可以选择将两个相邻且大小相同的数字合并，在这里我们定义合并之后数字大小增加1，如：4和4合并后变为5。

Input Format

第一行有一个正整数$t(1≤t≤10)$，表示有$t$组测试样例。

对于每个测试样例，第一行输入一个正整数$n(1≤n≤200)$，表示接下来会有$n$个正整数用于描述一个游戏地图。第二行输入$n$个正整数$ai(1≤ai≤40)$，表示地图中每个数字的大小。

Output Format

对于每一组测试样例，输出一行，包含一个正整数，表示能获得的最高分数。

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

3
4

Hint

对于第一组测试样例：

我们首先可以合并第二和第三个$1$，原数列变为：$1,2,2$。

接着，我们合并第二个和第三个$2$，数列变为：$1, 3$。

至此，无法继续合并，最后答案为$3$。

对于第二组测试样例：

我们首先可以合并第一个和第二$1$，原数列变为：$2, 2, 2, 2$。

接着，我们合并第一个和第二个$2$，以及合并第三个和第四个$2$，数列变为：$3, 3$。

最后，我们合并第一个和第二个$3$，数列变为：$4$。

至此，无法继续合并，最后答案为$4$。

Source

Online Judge http://127.0.0.1