Cho hai xâu \(S\) và \(T\) đều có độ dài là \(N\) và chỉ chứa hai ký tự là \(0\) và \(1\). Bạn có thể thực hiện trên xâu \(S\) phép toán sau với số lượng bất kỳ:

• Chọn chỉ số \(i(2\le i\le N)\) sao cho \(S[i]=1\) và thay thế \(S[i]=0\) và sau đó gán \(S[i-1]=1-S[i-1]\).

Chú ý: Chỉ số của xâu đánh từ số \(1\).

Hỏi: Ta có thể biến xâu \(S\) thành xâu \(T\) hay không ? Nếu có thì in ra số lượng phép toán tối thiểu cần dùng. Ngược lại, in ra \(-1\)

Input

• Dòng thứ nhất chứa số \(t\) - Thể hiện số testcase

• \(t\) block tiếp theo, mỗi block có dạng:

  \(N\text{ }\)

  \(S\text{ }\)

  \(T\).

  Với \(1\le N\le 5.10^5\).

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm

Example

2
2
01
10
2
00
11

1
-1