AT_arc216_a [ARC216A] Reversi 3

You are given strings $ A $ and $ B $ of length $ N $ consisting of `0` and `1`. Let $ A_i $ denote the $ i $ -th character of $ A $ . You can perform the following operation any number of times, possibly zero. - Choose an integer $ i\ (2 \leq i \leq N-1) $ satisfying $ A_{i-1} = A_{i+1} $ , and flip $ A_i $ (change `1` to `0` or `0` to `1`). Determine whether you can make $ A $ equal to $ B $ by repeating the operation, and if so, find the minimum number of operations required. You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ Each test case is given in the following format: > $ N $ $ A $ $ B $

Output the answers for $ \mathrm{case}_1, \mathrm{case}_2, \ldots, \mathrm{case}_T $ in the following format. If it is impossible to make $ A $ equal to $ B $ , print `-1`. If it is possible, print the minimum number of operations required.

### Sample Explanation 1 For the first test case, you can make $ A $ equal to $ B $ in two operations as follows. 1. Choose $ i = 2 $ . $ A $ becomes `0101`. 2. Choose $ i = 3 $ . $ A $ becomes `0111`. For the second test case, it is impossible to make $ A $ equal to $ B $ no matter how you operate. ### Constraints - $ 1 \leq T \leq 2 \times 10^5 $ - $ 3 \leq N \leq 10^6 $ - $ A $ and $ B $ are strings of length $ N $ consisting of `0` and `1`. - $ T $ and $ N $ are integers. - The sum of $ N $ over all test cases is at most $ 10^6 $ .