题目描述

小蓝用黑白棋的 $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 \limits_{i=1}^{D} n_i \leq 10$；

对于所有评测用例，保证 $1 \leq \sum \limits_{i=1}^{D} n_i \leq 10^6$，$n_i > 0$。