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.