Sum Over Subarrays

Given a binary string $S$, define $f(S) = \max ( \text{\# 0s in S, \# 1s in S})$, i.e. the the maximum among frequency of $0$ and frequency of $1$. Find the sum of $f$ over all substrings of $S$. Formally, compute $\sum_{L = 1}^{N} \sum_{R = L}^{N} f(S_L S_{L + 1} ... S_R)$. ### Input - The first line of input will contain a single integer $T$, denoting the number of test cases. - Each test case