Busy Beaver 正在为 MIT Mystery Hunt 做准备！他正在两个仅由字母 $\texttt{A}$ 和 $\texttt{B}$ 组成的字符串 $S_1$ 和 $S_2$ 上玩一个游戏。他可以对 $S_1$ 执行任意次数（可能为零）以下操作：

• 将任意连续子串 $\texttt{AAB}$ 替换为 $\texttt{BAA}$，反之亦然。
• 将任意连续子串 $\texttt{BBA}$ 替换为 $\texttt{ABB}$，反之亦然。

求将 $S_1$ 转换为 $S_2$ 所需的最少操作次数，如果无法转换，则输出 $-1$。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^3$)，表示测试用例的数量。

每个测试用例仅包含一行，由两个空格分隔的字符串 $S_1$ 和 $S_2$ ($1\le |S_1| = |S_2|\le 10^5$) 组成，字符串仅由字符 $\texttt{A}$ 和 $\texttt{B}$ 构成。

所有测试用例中字符串的总长度不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出将 $S_1$ 转换为 $S_2$ 所需的最少操作次数。如果无法转换，输出 $-1$。

子任务

本题共有三个子任务：

• ($10$ 分) $S_1$ 和 $S_2$ 中均恰好包含一个 $\texttt{B}$。
• ($20$ 分) $S_1$ 仅由若干个 $\texttt{A}$ 后接若干个 $\texttt{B}$ 组成，$S_2$ 仅由若干个 $\texttt{B}$ 后接若干个 $\texttt{A}$ 组成。
• ($70$ 分) 无附加限制。

样例

输入 1

1
AABBB BABBA

输出 1

2

说明

在第一个测试用例中，我们可以执行两次操作：$\color{red}{\texttt{AAB}}\texttt{BB} \to \color{blue}{\texttt{BAA}}\texttt{BB}$，然后 $\texttt{BA}\color{red}{\texttt{ABB}} \to \texttt{BA}\color{blue}{\texttt{BBA}}$。

输入 2

1
AAAAAABBB BBBAAAAAA

输出 2

9