Ones

A binary string is a string that consists of only the character $0$ and $1$. For example: $1010, 0, 11$ are binary strings.

Bob was given a problem to solve by his teacher. The problem is about binary strings. As Bob has recently started learning about strings, he is not quite sure if he can solve the problem. But maybe he can if you give him some hints $!$

The problem as follows: You are given two binary string $A$ and $B$. Consider a set $S = (i_1, i_2,..., i_k)$ that contains all the indices $i$ such that $A[i] = 1$. Similarly, let $T = (j_1, j_2,..., j_r)$ that contains all the indices $j$ such that $B[j] = 1$. Now you have to find the sum of $|i - j|$ for all $i$ and $j$ such that $i$ belongs to $S$ and $j$ belongs to $T$.

More formally, find the value of $\sum\limits_{i \in S}^{j \in T} |i - j|$

To give hints to Bob, you show him only this value but not the actual solution or how to do it.

For example, let $A = 101, B = 110.$ Then, $S = (1, 3)$ and $T = (1, 2).$ So the answer is: $|1 - 1| + |1 - 2| + |3 - 1| + |3 - 2| = 0 + 1 + 2 + 1 = 4.$

Note that $|x|$ denotes the absolute value of $x.$

Input

The first line contains an integer $T$ the number of test cases $(1 \leq T \leq 10^3)$.

For each test case, the first line contains an integer $n$ $(1 \leq n \leq 10^5)$ — the size of the binary string $A$ and $B$. The next two line contains the binary string $A$ and $B$ respectively.

It is guaranteed that both $A$ and $B$ are binary string. It is also guaranteed that the sum of $n$ over all test cases does not exceed $10^5.$

Output

For each test case, print the value described above.

Sample

Input	Output
3 2 01 01 3 101 110 6 101010 011011	0 4 24