問題文

正整数 $N$ と、長さ $N$ の $0$ を除く数字, +, -, * からなる数式 $F$ が与えられます。
より厳密には、以下の BNF 記法の <expr> シンボルに従う $\color{red} ^{*1}$ 長さ $N$ の文字列 $F$ が与えられます。

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

$1 \le p \le N$ なる整数 $p$ と、 $\color{red}0$ を除く数字 $c$ の組 $(p, c)$ のうち、以下の条件を満たすものの個数を求めてください。

• $F$ の $p$ 文字目を $c$ に置き換えた文字列を $G$ とする。 $G$ の計算結果は $F$ の計算結果よりも真に大きい。

ここで、本問題においていかなる $(p, c)$ であっても $G$ が <expr> シンボルに従うことが証明できます。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• $T$ は $1 \leq T \leq 10^4$ を満たす整数である。
• 各テストケースは以下の制約をすべて満たす。
• $N$ は $1 \leq N \leq 2.5 \times 10^5$ を満たす整数である。
• $F$ は問題文中の <expr> シンボルに従う長さ $N$ の文字列である。
• 一つの入力ファイルにおける $N$ の総和は $5 \times 10^5$ を超えない。

入力

入力は以下の形式で標準入力から与えられます。ここで、$\mathrm{case}_t ~ (1 \leq t \leq T)$ は $t$ 番目のテストケースを表します。

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

各テストケースは以下の形式で標準入力から与えられます。

$N$
$F$

出力

$T$ 行出力してください。$t$ 行目には $t$ 番目のテストケースについての答えを出力してください。

サンプル

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