In order to test his patients' intelligence, Dr. TC created the following test.

First, he creates a binary string$^{\text{∗}}$ $s$ having $n$ characters. Then, he creates $n$ binary strings $a_1, a_2, \ldots, a_n$. It is known that $a_i$ is created by first copying $s$, then flipping the $i$'th character (1 becomes 0 and vice versa). After creating all $n$ strings, he arranges them into a grid where the $i$'th row is $a_i$.

For example,

• If $s = \texttt{101}$, $a = [\texttt{001}, \texttt{111}, \texttt{100}]$.
• If $s = \texttt{0000}$, $a = [\texttt{1000}, \texttt{0100}, \texttt{0010}, \texttt{0001}]$.

The patient needs to count the number of $1$s written on the board in less than a second. Can you pass the test?

$^{\text{∗}}$A binary string is a string that only consists of characters 1 and 0.

Input

The first line of the input consists of a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10$) — the length of the binary string $s$.

The second line of each test case contains a single binary string $s$ of size $n$.

Output

For each test case, output a single integer, the number of 1s on the board.

Note

The first example is explained in the statement.

For the second example, the only string written on the board will be the string 0; therefore, the answer is $0$.

In the third example, the following strings will be written on the board: $[\texttt{10000}, \texttt{01000}, \texttt{00100}, \texttt{00010}, \texttt{00001}]$; so there are five 1s written on the board.

Samples

5
3
101
1
1
5
00000
2
11
3
010

5
0
5
2
4