The 2018 ICPC Asia Qingdao Regional Programming Contest (The 1st Universal Cup, Stage 9: Qingdao) |
---|
Finished |
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:
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:
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$$$.
For each test case, output an integer denoting the answer.
3
1
1
0
2
00
11
5
01010
00111
0
2
6
For 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)$$$.
Name |
---|