
155  The 2018 ACMICPC Asia Qingdao Regional Contest (Mirror)  C
DreamGrid has just found two binary sequences $s_1, s_2, \dots, s_n$ and $t_1, t_2, \dots, t_n$ ($s_i, t_i \in \{0, 1\}$ for all $1 \le i \le n$) from his virtual machine! He would like to perform the operation described below exactly twice, so that $s_i = t_i$ holds for all $1 \le i \le n$ after the two operations. The operation is: Select two integers $l$ and $r$ ($1 \le l \le r \le n$), change $s_i$ to $(1  s_i)$ for all $l \le i \le r$. DreamGrid would like to know the number of ways to do so. We use the following rules to determine whether two ways are different:
InputThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case: The first line contains an integer $n$ ($1 \le n \le 10^6$), indicating the length of two binary sequences. The second line contains a string $s_1s_2\dots s_n$ ($s_i \in \{\text{'0'}, \text{'1'}\}$) of length $n$, indicating the first binary sequence. The third line contains a string $t_1t_2\dots t_n$ ($t_i \in \{\text{'0'}, \text{'1'}\}$) of length $n$, indicating the second binary sequence. It's guaranteed that the sum of $n$ in all test cases will not exceed $10^7$. OutputFor each test case, output an integer denoting the answer. Sample Input3 1 1 0 2 00 11 5 01010 00111 Sample Output0 2 6 HintFor the second sample test case, there are two valid operation pairs: (1, 1, 2, 2) and (2, 2, 1, 1). For the third sample test case, there are six valid operation pairs: (2, 3, 5, 5), (5, 5, 2, 3), (2, 5, 4, 4), (4, 4, 2, 5), (2, 4, 4, 5) and (4, 5, 2, 4). 