A. Доктор ТС
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Чтобы проверить интеллект своих пациентов, доктор ТС создал следующий тест.

Сначала он создает двоичную строку$$$^{\text{∗}}$$$ $$$s$$$ длиной $$$n$$$ символов. Затем он создает $$$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$$$.

Вторая строка каждого набора входных данных содержит одну двоичную строку $$$s$$$ длины $$$n$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество $$$\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}$$$.