|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|2 초||512 MB||16||8||8||50.000%|
Peter hasn't submitted his homework for today's Computer Science lesson, so he is punished and given an additional task. The teacher has written two strings of the same length at the blackboard and asks Peter to make them equal using operations of only one type: take two adjacent characters of one of the strings and invert them both. Inversion transforms 0 to 1 and 1 to 0.
To make the problem even harder, Peter must use the minimal number of inversion operations.
Help Peter to complete his difficult task.
For example, if the two strings were "0101" and "1111" one way to make them equal is to invert two characters in the middle of the first string to get "0011" and "1111" and then invert two first characters of the second string to get "0011" and "0011". Note that there are other ways to complete the task with two operations in this example.
Input data contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 100).
Each test case is described in the following way. The first line contains n (1 ≤ n ≤ 105) — the length of the strings written by the teacher. The second and the third lines contain the strings themselves — two strings of length n containing only 0-s and 1-s.
The sum of values of n for all test cases in one input data doesn't exceed 105.
For each test case print one line: the minimal required number of inversion operations to make the strings equal, or - 1 if it is impossible to make the strings equal.
2 4 0101 1111 3 011 111