F. AAB ↔ BAA
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver is preparing for the MIT Mystery Hunt! He is playing a game on two strings $$$S_1$$$ and $$$S_2$$$, each consisting only of the letters $$$\texttt{A}$$$ and $$$\texttt{B}$$$. He can perform the following operation any number of times (possibly zero) on $$$S_1$$$:

  • Replace any contiguous substring $$$\texttt{AAB}$$$ with a contiguous substring $$$\texttt{BAA}$$$, or vice versa.
  • Replace any contiguous substring $$$\texttt{BBA}$$$ with a contiguous substring $$$\texttt{ABB}$$$, or vice versa.

Find the minimum number of operations needed to transform $$$S_1$$$ into $$$S_2$$$, or report that this is impossible.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^3$$$) — the number of test cases.

The only line of each test case contains two space-separated strings $$$S_1$$$ and $$$S_2$$$ ($$$1\le |S_1| = |S_2|\le 10^5$$$) consisting of characters $$$\texttt{A}$$$ and $$$\texttt{B}$$$.

The total length of all strings across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print the minimum number of operations you need to transform $$$S_1$$$ into $$$S_2$$$. If this is impossible, output $$$-1$$$.

Scoring

There are three subtasks for this problem.

  • ($$$10$$$ points) There exists exactly one $$$\texttt{B}$$$ in both $$$S_1$$$ and $$$S_2$$$.
  • ($$$20$$$ points) $$$S_1$$$ consists only of $$$\texttt{A}$$$s followed by $$$\texttt{B}$$$s, and $$$S_2$$$ consists only of $$$\texttt{B}$$$s followed by $$$\texttt{A}$$$s.
  • ($$$70$$$ points) No additional constraints.
Examples
Input
1
AABBB BABBA
Output
2
Input
1
AAAAAABBB BBBAAAAAA
Output
9
Note

In the first test case, we can perform two operations: $$$\color{red}{\texttt{AAB}}\texttt{BB} \to \color{blue}{\texttt{BAA}}\texttt{BB}$$$ and then $$$\texttt{BA}\color{red}{\texttt{ABB}} \to \texttt{BA}\color{blue}{\texttt{BBA}}$$$.