Problem Statement

You are given a positive integer $N$ and a formula $F$ of length $N$ consisting of digits other than $0$, +, -, and *.
More precisely, you are given a string $F$ of length $N$ that conforms to $\color{red} ^{*1}$ the <expr> symbol of the following BNF.

<expr>   ::= <term> | <expr> "+" <term> | <expr> "-" <term>
<term>   ::= <number> | <term> "*" <number>
<number> ::= <digit> | <digit> <number>
<digit>  ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

Find the number of pairs $(p, c)$ of an integer $p$ with $1 \le p \le N$ and a digit $c$ other than $\color{red}0$ that satisfy the following condition.

• Let $G$ be the string obtained by replacing the $p$-th character of $F$ with $c$. The value of $G$ is strictly greater than the value of $F$.

Here, it can be proved that in this problem $G$ conforms to the <expr> symbol for any $(p, c)$.

You are given $T$ test cases; answer each of them.

Constraints

• $T$ is an integer satisfying $1 \leq T \leq 10^4$.
• Each test case satisfies all of the following constraints.
• $N$ is an integer satisfying $1 \leq N \leq 2.5 \times 10^5$.
• $F$ is a string of length $N$ that conforms to the <expr> symbol in the problem statement.
• The sum of $N$ in a single input file does not exceed $5 \times 10^5$.

Input

The input is given from standard input in the following format. Here, $\mathrm{case}_t ~ (1 \leq t \leq T)$ denotes the $t$-th test case.

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given from standard input in the following format.

$N$
$F$

Output

Output $T$ lines. On the $t$-th line, output the answer to the $t$-th test case.

Sample

4
7
3+14*15
7
123-987
1
9
63
122333444455555666666777777788888888999999999+1-2*3+4-5*6+7*8-9

49
51
0
201