题目描述

为了测试病人的智力水平，TC 医生设计了以下测试。

首先，他创建一个长度为 $n$ 的二进制字符串$^{\text{∗}}$ $s$。然后，他创建 $n$ 个二进制字符串 $a_1, a_2, \ldots, a_n$。已知 $a_i$ 是通过先复制 $s$，然后翻转第 $i$ 个字符（$\texttt{1}$ 变为 $\texttt{0}$，反之亦然）得到的。创建完所有 $n$ 个字符串后，他将它们排列成一个网格，其中第 $i$ 行是 $a_i$。

例如：

• 如果 $s = \texttt{101}$，则 $a = [\texttt{001}, \texttt{111}, \texttt{100}]$；
• 如果 $s = \texttt{0000}$，则 $a = [\texttt{1000}, \texttt{0100}, \texttt{0010}, \texttt{0001}]$。

病人需要在不到一秒的时间内计算出黑板上所有 $\texttt{1}$ 的数量。你能通过这个测试吗？

$^{\text{∗}}$ 二进制字符串是指仅由字符 $\texttt{1}$ 和 $\texttt{0}$ 组成的字符串。

输入格式

输入的第一行包含一个整数 $t$（$1 \le t \le 1000$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10$）——二进制字符串 $s$ 的长度。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$。

输出格式

对于每个测试用例，输出一个整数，表示黑板上所有 $\texttt{1}$ 的数量。

说明/提示

第一个样例已在题目描述中解释。

对于第二个样例，黑板上唯一的字符串是 $\texttt{0}$，因此答案是 $0$。

在第三个样例中，黑板上将显示以下字符串：$[\texttt{10000}, \texttt{01000}, \texttt{00100}, \texttt{00010}, \texttt{00001}]$，所以黑板上共有 $5$ 个 $\texttt{1}$。

翻译由 DeepSeek V3 完成

样例

5
3
101
1
1
5
00000
2
11
3
010

5
0
5
2
4