You are given a binary string $S$ of length $N$. A substring of a binary string is called positive if the number of $1's$ present in the substring is strictly greater than the number of $0's$ present. Find the number of positive substrings in the given string $S$

  Input format

• The first line contains $T$ denoting the number of test cases. The description of $T$ test cases is as follows:
• For each test case:
  • The first line contains $N$ denoting the length of string $S$.
  • The second line contains the binary string $S$.

Output format

For each test case, print  the number of positive substrings in the given string $S$

Constraints

$1 \leq T \leq 10^5 \\ 1 \leq N \leq 3\cdot10^5\\ \\S \; contains\; '0's\; and\; '1's. \\ Sum\; of \; N\;over\;all\;test\;cases\;does\;not\;exceed\;3\cdot 10^5.$