AAB ↔ BAA

면접 대비

시간 제한1초메모리 제한256 MB

요약

AAB를 BAA로, BBA를 ABB로 바꾸는 연산만 쓸 수 있을 때 S1을 S2로 만드는 최소 연산 횟수를 구하거나 불가능하면 -1을 출력한다.

난이도: 보통10점 중 7점
유형: 문자열, 그리디, 수학, 구현
정답자: 아직 제출이 없습니다

문제

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.

예제2

예제 1
입력
```
1
AABBB BABBA
```
예상 출력
```
2
```
예제 2
입력
```
1
AAAAAABBB BBBAAAAAA
```
예상 출력
```
9
```