Problem Description

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.

Input Format

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$.

Output Format

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

3
4
2432
8
19919911
16
1991991119919911

65
292
656

Hint

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}

• Special Property A: $n_i \le 2$.