P16279 「MierOI R1」Future

Given a $k$-digit decimal number $N=\overline{n_1n_2\dots n_k}$. **It is guaranteed that $\bm k$ is even, and $\bm{n_i \ne 0}$.** You can perform the following operation exactly $\frac{k}{2}$ times: - Delete any two adjacent digits $n_i,n_{i+1}$ in $N$, and gain $\overline{n_in_{i+1}}$ points. **The remaining digits are automatically concatenated.** Find the maximum total score.

**This problem contains multiple test cases.** The first line of the input contains a positive integer $T$, indicating the number of test cases. Then, the $T$ test cases follow sequentially. For each test case: - The first line contains a single positive integer $k$. - The second line contains a $k$-digit decimal number $N$.

For each test case, output a single line containing an integer, representing the maximum total score.

#### Explanation for Sample #1 For the first test case, the optimal sequence of operations is as follows: - Delete digits $n_2=4,n_3=3$, gaining $43$ points. $N$ becomes $22$. - Delete digits $n_1=2,n_2=2$, gaining $22$ points. $N$ becomes empty. The total score is $43+22=65$ points. It can be proven that this is the maximum total score. #### Data Range **This problem uses bundled subtasks.** For all test cases, it is guaranteed that $1 \le T \le 5$, $2 \le k \le 10^5$, and $1 \le n_i \le 9$. ::cute-table{tuack} | Subtask | $k \le$ | Special Property | Score | |:-:|:-:|:-:|:-:| | $1$ | $10$ | None | $20$ | | $2$ | $10^3$ | ^ | $20$ | | $3$ | $10^5$ | A | $20$ | | $4$ | ^ | None | $40$ | - Special Property A: $n_i \le 2$.