← 返回题目列表

Codeforces · 2106/A

A. TC博士

中文机器翻译题面 查看原题

为了测试患者的智力,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}]$$$。

患者需要在不到一秒的时间内数出黑板上写的 $$$1$$$ 的数量。你能通过测试吗?

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

输入

输入的第一行由一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) 组成 - 测试用例的数量。

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

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

输出

对于每个测试用例,输出一个整数,即板上 $$$\texttt{1}$$$ 的数量。

示例

输入
复制

5
3
101
1
1
5
00000
2
11
3
010

输出
复制

5
0
5
2
4

注意

第一个示例在语句中进行了解释。

对于第二个示例,板上写的唯一字符串将是字符串 $$$\texttt{0}$$$;因此,答案是$$$0$$$。

在第三个示例中,将在板上写入以下字符串:$$$[\texttt{10000}, \texttt{01000}, \texttt{00100}, \texttt{00010}, \texttt{00001}]$$$;所以黑板上写着五个 $$$\texttt{1}$$$。