{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eDreamGrid 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 \u003d t_i$ holds for all $1 \\le i \\le n$ after the two operations.\u003c/p\u003e\r\n\r\n\u003cp\u003eThe 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$.\u003c/p\u003e\r\n\r\n\u003cp\u003eDreamGrid would like to know the number of ways to do so.\u003c/p\u003e\r\n\r\n\u003cp\u003eWe use the following rules to determine whether two ways are different:\u003c/p\u003e\r\n\r\n\u003cul\u003e\r\n \u003cli\u003eLet $A \u003d (a_1, a_2, a_3, a_4)$, where $1 \\le a_1 \\le a_2 \\le n, 1 \\le a_3 \\le a_4 \\le n$, be a valid operation pair denoting that DreamGrid selects integers $a_1$ and $a_2$ for the first operation and integers $a_3$ and $a_4$ for the second operation;\u003c/li\u003e\r\n \u003cli\u003eLet $B \u003d (b_1, b_2, b_3, b_4)$, where $1 \\le b_1 \\le b_2 \\le n, 1 \\le b_3 \\le b_4 \\le n$, be another valid operation pair denoting that DreamGrid selects integers $b_1$ and $b_2$ for the first operation and integers $b_3$ and $b_4$ for the second operation.\u003c/li\u003e\r\n \u003cli\u003e$A$ and $B$ are considered different, if there exists an integer $k$ ($1 \\le k \\le 4$) such that $a_k \\ne b_k$.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch4\u003eInput\u003c/h4\u003e\r\n\u003cp\u003eThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:\u003c/p\u003e\r\n\r\n\u003cp\u003eThe first line contains an integer $n$ ($1 \\le n \\le 10^6$), indicating the length of two binary sequences.\u003c/p\u003e\r\n\r\n\u003cp\u003eThe second line contains a string $s_1s_2\\dots s_n$ ($s_i \\in \\{\\text{\u00270\u0027}, \\text{\u00271\u0027}\\}$) of length $n$, indicating the first binary sequence.\u003c/p\u003e\r\n\r\n\u003cp\u003eThe third line contains a string $t_1t_2\\dots t_n$ ($t_i \\in \\{\\text{\u00270\u0027}, \\text{\u00271\u0027}\\}$) of length $n$, indicating the second binary sequence.\u003c/p\u003e\r\n\r\n\u003cp\u003eIt\u0027s guaranteed that the sum of $n$ in all test cases will not exceed $10^7$.\u003c/p\u003e\r\n\r\n\u003ch4\u003eOutput\u003c/h4\u003e\r\n\u003cp\u003eFor each test case, output an integer denoting the answer.\u003c/p\u003e\r\n\r\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n1\r\n1\r\n0\r\n2\r\n00\r\n11\r\n5\r\n01010\r\n00111\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n2\r\n6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\r\n\u003ch4\u003eHint\u003c/h4\u003e\r\n\u003cp\u003eFor the second sample test case, there are two valid operation pairs: (1, 1, 2, 2) and (2, 2, 1, 1).\u003c/p\u003e\r\n\r\n\u003cp\u003eFor 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).\u003c/p\u003e"}}]}