### 问题描述 小蓝用黑白棋的 $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 1000111 1010101 01000 11000 ``` ### 样例输出 ``` 2 -1 ``` ### 评测用例规模与约定 对于 $20\%$ 的评测用例，$1 \leq \sum^D_1 n_i \leq 10$； 对于所有评测用例，保证 $1 \leq \sum_1^D n_i \leq 10^6$，$n_i > 0$。