{"raw_statement":[{"iden":"statement","content":"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.\n\nThe 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$.\n\nDreamGrid would like to know the number of ways to do so.\n\nWe use the following rules to determine whether two ways are different:\n\n- Let $A = (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;\n- Let $B = (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.\n- $A$ and $B$ are considered different, if there exists an integer $k$ ($1 \\le k \\le 4$) such that $a_k \\ne b_k$."},{"iden":"input","content":"There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:\n\nThe first line contains an integer $n$ ($1 \\le n \\le 10^6$), indicating the length of two binary sequences.\n\nThe 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.\n\nThe 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.\n\nIt's guaranteed that the sum of $n$ in all test cases will not exceed $10^7$."},{"iden":"output","content":"For each test case, output an integer denoting the answer."},{"iden":"note","content":"For the second sample test case, there are two valid operation pairs: $(1, 1, 2, 2)$ and $(2, 2, 1, 1)$.\n\nFor 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)$."}],"translated_statement":null,"sample_group":[["3\n1\n1\n0\n2\n00\n11\n5\n01010\n00111","0\n2\n6"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}