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.
Example
Input
1 AABBB BABBA
Output
2
Explanation
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}}$.
Input
1 AAAAAABBB BBBAAAAAA
Output
9