为了测试患者的智力,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}$$$ 的数量。
示例
输入复制
53101115000002113010
输出复制
5 0 5 2 4
注意
第一个示例在语句中进行了解释。
对于第二个示例,板上写的唯一字符串将是字符串 $$$\texttt{0}$$$;因此,答案是$$$0$$$。
在第三个示例中,将在板上写入以下字符串:$$$[\texttt{10000}, \texttt{01000}, \texttt{00100}, \texttt{00010}, \texttt{00001}]$$$;所以黑板上写着五个 $$$\texttt{1}$$$。