Problem C. 奇怪的开关II

时间限制：2000ms

内存限制：256MB

Background

前文见悬赏令3C

自从小王同学成功地从那个房子里走了出来后，那房子就消失了。可是这天小王在路上走着，发现那个房子又出现了。小王感觉很神奇，一个房子能凭空消失又再次出现。有了上次的经验，小王再次走了进去，这次场景和之前差不多，但是纸条的内容变了。

Description

这次纸条的意思是房子一共有 \(n\) 个房间，每个房间都有一些灯泡，状态用 \(0\) 和 \(1\) 表示（\(0\)表示关闭，\(1\)表示打开）。现在每个灯泡都有一个奇怪的开关，按下这个开关，**如果对应的灯泡是亮的，那么除了对应的灯泡其他灯泡都会变成相反的状态；否则将不会发生任何事情**。每个房间所有灯泡的状态可以组成一个 \(01\) 串 \(s\) 。每个房间都有一个目标 \(01\) 串 \(t\) ，只有找到每个房间内将灯泡状态 \(s\) 变为目标状态 \(t\) 的最短操作次数，或者报告这不可能实现，小王才能再次从这个房子里出去。

Input

第一行一个整数 \(n\) ，代表 \(n\) 个房间。

每个房间的输入有三行。第一行一个整数 \(m\) ，\(m\) 表示灯泡总数；

第二行是一个 \(01\) 串，代表着房间初始灯泡状态。

第三行也是一个 \(01\) 串，代表着目标状态。

Output

每个房间输出一个整数，非负整数代表最小操作次数，\(-1\) 代表不可能变成目标状态。

Sample Input

2
9
100010111
101101100
3
000
101

Sample Output

3
-1

解释：第一个房间的操作方式为

100010\(\color{Red}1\)11 -> 011101\(\color{Red}1\)00

0\(\color{Red}1\)1101100 -> 1\(\color{Red}1\)0010011

\(\color{Red}1\)10010011 -> \(\color{Red}1\)01101100

Data range

对于50% 数据，\(1 \leq \sum m \leq 1000\)；
对于 100% 数据，\(1 \leq \sum m \leq 10^5\)，\(1 \leq n \leq 10^4\)。