布丁的翻转牌游戏

描述

布丁最近发明了个有趣的游戏，她准备拿给她的朋友们一起玩。 游戏的规则如下：

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

例如：

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

游戏的目标是在不到一秒钟的时间内数出写在板上的 1 的总数。你能帮助布丁和他的朋友们快速找到答案吗？

输入

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

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

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

输出

对于每个测试用例，输出一个整数，即板上 1 的总数。

示例

5
3
101
1
1
5
00000
2
11
3
010

5
0
5
2
4

说明

• 第一个例子在题目描述中已经解释。
• 第二个例子中，板上唯一的字符串是 0，因此答案是 0。
• 第三个例子中，板上的字符串为 [10000, 01000, 00100, 00010, 00001]，因此板上有 5 个 1。