Pisces likes 0s! In his opinion, 0 is the ultimate of everything and the eternal answer to all questions. He thinks a string is perfect if it only contains 0s. Now given a binary string of length \(n\), Pisces wants to know how many perfect substrings it has.

The first line contains an integer \(T(1\leq T\leq 10)\), which represents the number of test cases.

For each of the test case, the first line is an integer \(n(1\leq n\leq 10^5)\), which is the length of the given string. The second line is a binary string of length \(n\).

For each test case, print the number of perfect substrings in the given string.