C. Менора
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть особая версия меноры: она состоит из $$$n$$$ свечей и некоторые из них уже зажжены. Мы можем описать, какие из свечей горят, с помощью бинарной строки $$$s$$$, где $$$i$$$-я свечка горит тогда и только тогда, когда $$$s_i=1$$$.

Первоначально, горящие свечки описаны строкой $$$a$$$. За одну операцию, вы можете выбрать любую горящую в данный момент свечку — выбранная свеча продолжит гореть, а каждая из других свечей изменит свое состояние (если она горела, то потухнет, а если не горела — то загорится).

Вы хотите, чтобы в результате свечи горели так, как описывает строка $$$b$$$. Ваша задача определить, возможно ли это и какое наименьшее количество операций нужно будет совершить.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1\le t\le 10^4$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$1\le n\le 10^5$$$) — количество свечей.

Во второй строке каждого набора задана строка $$$a$$$ длины $$$n$$$, состоящая из символов 0 и 1 — первоначально состояние свечей.

В третьей строке задана строка $$$b$$$ длины $$$n$$$, состоящая из символов 0 и 1 — желаемое состояние свечей.

Гарантируется, что сумма $$$n$$$ не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите наименьшее количество операций, чтобы превратить $$$a$$$ в $$$b$$$, или же $$$-1$$$, если это невозможно.

Пример
Входные данные
5
5
11010
11010
2
01
11
3
000
101
9
100010111
101101100
9
001011011
011010101
Выходные данные
0
1
-1
3
4
Примечание

В первом наборе входных данных, две строки уже равны, а потому нам не нужно применять ни одной операции.

Во втором наборе, мы можем применить одну операцию, выбрав вторую свечку, и превратить $$$01$$$ в $$$11$$$.

В третьем наборе, невозможно применить ни одной операции, потому что нет ни одной горящей свечи, которую можно выбрать.

В четвертом наборе, мы можем применить следующие операции, чтобы превратить $$$a$$$ в $$$b$$$:

  1. Выберем $$$7$$$-ю свечу: $$$100010{\color{red}1}11\to 011101{\color{red} 1}00$$$.
  2. Выберем $$$2$$$-ю свечу: $$$0{\color{red} 1}1101100\to 1{\color{red} 1}0010011$$$.
  3. Выберем $$$1$$$-ю свечу: $$${\color{red}1}10010011\to {\color{red}1}01101100$$$.

В пятом наборе, мы можем применить следующие операции, чтобы превратить $$$a$$$ в $$$b$$$:

  1. Выберем $$$6$$$-ю свечу: $$$00101{\color{red}1}011\to 11010{\color{red}1}100$$$
  2. Выберем $$$2$$$-ю свечу: $$$1{\color{red}1}0101100\to 0{\color{red}1}1010011$$$
  3. Выберем $$$8$$$-ю свечу: $$$0110100{\color{red}1}1\to 1001011{\color{red}1}0$$$
  4. Выберем $$$7$$$-ю свечу: $$$100101{\color{red}1}10\to 011010{\color{red}1}01$$$