问题描述

小蓝用黑白棋的 $n$ 个棋子排成了一行，他在脑海里想象出了一个长度为 $n$ 的 01 串 $T$ ，他发现如果把黑棋当做 1，白棋当做 0，这一行棋子也是一个长度为 $n$ 的 01 串 $S$ 。

小蓝决定，如果在 $S$ 中发现一个棋子和它两边的棋子都不一样，就可以将其翻转变成另一个颜色。也就是说，如果 $S$ 中存在子串 101 或者 010，就可以选择将其分别变为 111 和 000，这样的操作可以无限重复。

小蓝想知道最少翻转多少次可以把 $S$ 变成和 $T$ 一模一样。

输入格式

输入包含多组数据。

输入的第一行包含一个正整数 $D$ 表示数据组数。

后面 $2D$ 行每行包含一个 01 串，每两行为一组数据，第 $2i−1$ 行为第 $i$ 组数据的 $T_i$ ，第 $2i$ 行为第 $i$ 组数据的 $S_i$ ， $S_i$ 和 $T_i$ 长度均为 $n_i$ 。

对于每组数据，输出一行包含一个整数，表示答案，如果答案不存在请输出 -1。

2
-1

对于 $20\%$ 的评测用例， $1≤\sum_1^Dn_i≤10$ ；

对于所有评测用例，保证 $1≤\sum_1^Dn_i≤10^6$ ， $n_i>0$ 。