A. Dr. TC

time limit per test

1 second

memory limit per test

256 megabytes

In order to test his patients' intelligence, Dr. TC created the following test.

First, he creates a binary string∗∗ ss having nn characters. Then, he creates nn binary strings a1,a2,…,ana1,a2,…,an. It is known that aiai is created by first copying ss, then flipping the ii'th character (11 becomes 00 and vice versa). After creating all nn strings, he arranges them into a grid where the ii'th row is aiai.

For example,

• If s=101s=101, a=[001,111,100]a=[001,111,100].
• If s=0000s=0000, a=[1000,0100,0010,0001]a=[1000,0100,0010,0001].

The patient needs to count the number of 11s written on the board in less than a second. Can you pass the test?

∗∗A binary string is a string that only consists of characters 11 and 00.

Input

The first line of the input consists of a single integer tt (1≤t≤10001≤t≤1000) — the number of test cases.

The first line of each test case contains a single integer nn (1≤n≤101≤n≤10) — the length of the binary string ss.

The second line of each test case contains a single binary string ss of size nn.

Output

For each test case, output a single integer, the number of 11s on the board.

Example

Input

Copy

5

3

101

1

1

5

00000

2

11

3

010

Output

Copy

5
0
5
2
4

Note

The first example is explained in the statement.

For the second example, the only string written on the board will be the string 00; therefore, the answer is 00.

In the third example, the following strings will be written on the board: [10000,01000,00100,00010,00001][10000,01000,00100,00010,00001]; so there are five 11s written on the board.

解题说明：此题是一道数学题，找规律即可，首先统计出原来数字中包含多少个1，多少个0.翻转后就能发现总的1的数目是(n-1)*（1的个数)+（0的个数）

#include<stdio.h>
int main()
{int t;scanf("%d", &t);while (t--){int n, i, num;scanf("%d", &n);int sum = 0, arr[11];scanf("%d", &num);for (i = 0; i < n; i++){arr[i] = num % 10;sum += arr[i];num /= 10;}printf("%d\n", (sum * n) + n - (2 * sum));}return 0;
}