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