P16279 「MierOI R1」Future

给定一个 $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$。

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

#### 「样例 #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} | 子任务 | $k \le$ | 特殊性质 | 分值 | |:-:|:-:|:-:|:-:| | $1$ | $10$ | 无 | $20$ | | $2$ | $10^3$ | ^ | $20$ | | $3$ | $10^5$ | A | $20$ | | $4$ | ^ | 无 | $40$ | - 特殊性质 A：$n_i \le 2$。