{"raw_statement":[{"iden":"problem statement","content":"You are given two length-$N$ strings $A = A_1A_2 \\ldots A_N$ and $B = B_1B_2 \\ldots B_N$, each consisting of `0` and `1`.\nThere are $N$ squares aligned in a row from left to right. For $i = 1, 2, \\ldots, N$, the $i$\\-th square from the left is called square $i$. Initially, square $i$ contains a piece if $A_i = $ `1`, and no piece if $A_i = $ `0`.\nYou may repeat the following operation any number of times (possibly zero):\n\n*   Choose an integer $i$ between $1$ and $N$, inclusive.\n*   Move all pieces simultaneously one square closer to square $i$. That is, for each piece, let square $j$ be its current position and square $j'$ be its new position, and the following holds:\n    *   if $i < j$, then $j' = j-1$;\n    *   if $i > j$, then $j' = j+1$;\n    *   if $i = j$, then $j' = j$.\n\nDetermine whether it is possible to reach a configuration satisfying the following condition, and if it is possible, find the minimum number of operations needed to do so:\n\n> For every $i = 1, 2, \\ldots, N$, there is at least one piece in square $i$ if and only if $B_i = $ `1`.\n\nYou are given $T$ independent test cases. Print the answer for each of them."},{"iden":"constraints","content":"*   $1 \\leq T \\leq 2 \\times 10^5$\n*   $1 \\leq N \\leq 10^6$\n*   $T$ and $N$ are integers.\n*   $A$ and $B$ are strings of length $N$, each consisting of `0` and `1`.\n*   There exists $i$ such that $A_i = $ `1`.\n*   There exists $i$ such that $B_i = $ `1`.\n*   The sum of $N$ over all test cases is at most $10^6$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\mathrm{case}_2$\n$\\vdots$\n$\\mathrm{case}_T$\n\nHere, $\\mathrm{case}_i$ ($i=1,2,\\ldots,T$) denotes the $i$\\-th test case.\nEach test case is given in the following format:\n\n$N$\n$A$\n$B$"},{"iden":"sample input 1","content":"3\n8\n01001101\n00001011\n3\n010\n111\n20\n10100011011110101011\n00010001111101100000"},{"iden":"sample output 1","content":"3\n-1\n5\n\nThe input has three independent test cases.\nIn the first test case, initially, the sequence of the numbers of pieces in the squares is $(0, 1, 0, 0, 1, 1, 0, 1)$. By performing the operation three times as follows, you can satisfy the condition:\n\n*   Choose $i = 5$. After the operation, the configuration is $(0, 0, 1, 0, 2, 0, 1, 0)$.\n*   Choose $i = 8$. After the operation, the configuration is $(0, 0, 0, 1, 0, 2, 0, 1)$.\n*   Choose $i = 8$. After the operation, the configuration is $(0, 0, 0, 0, 1, 0, 2, 1)$.\n\nIt is impossible to satisfy the condition in fewer than three operations, so the answer is $3$.\nIn the second test case, no matter how you perform the operations, you cannot satisfy the condition, so the answer is `-1`."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}