34463번 - AAB ↔ BAA 서브태스크다국어

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 A and B. He can perform the following operation any number of times (possibly zero) on $S_1$:

• Replace any contiguous substring AAB with a contiguous substring BAA, or vice versa.
• Replace any contiguous substring BBA with a contiguous substring ABB, or vice versa.

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

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 A and B.

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

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$.

In the first test case, we can perform two operations: AABBB $\to$ BAABB and then BAABB $\to$ BABBA.