题目描述

给定一个 $k$ 位十进制数 $N=\overline{n_1n_2\dots n_k}$。保证 $\bm k$ 为偶数，且 $\bm{n_i \ne 0}$。

你可以执行以下操作恰好 $\frac{k}{2}$ 次：

• 删除 $N$ 中任意两个相邻的数位 $n_i,n_{i+1}$，获得 $\overline{n_in_{i+1}}$ 分。剩余数位自动拼接。

求总得分的最大值。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 $T$，表示测试数据的组数。

接下来依次输入 $T$ 组测试数据。对于每组测试数据：

• 第一行，一个正整数 $k$。
• 第二行，一个 $k$ 位十进制数 $N$。

输出格式

对于每组测试数据，输出一行一个整数，表示总得分的最大值。

3
4
2432
8
19919911
16
1991991119919911

65
292
656

提示

「样例 #1 解释」

对于第一组测试数据，最优操作方案如下：

• 删除数位 $n_2=4,n_3=3$，获得 $43$ 分，$N$ 变为 $22$。
• 删除数位 $n_1=2,n_2=2$，获得 $22$ 分，$N$ 被删空。

总得分为 $43+22=65$ 分。可以证明，这是最大总得分。

「数据范围」

本题采用子任务捆绑测试。

对于所有测试数据，保证 $1 \le T \le 5$，$2 \le k \le 10^5$，$1 \le n_i \le 9$。

::cute-table{tuack}

• 特殊性质 A：$n_i \le 2$。