문자열 변환

좋은 문자열은 다음과 같이 정의한다.

1. ab는 좋은 문자열이다.
2. 문자열 $S$가 좋은 문자열이면, 앞과 뒤에 각각 a와 b를 붙인 $aSb$도 좋은 문자열이다.
3. 문자열 $S$와 $T$가 좋은 문자열이면, 이어 붙인 $ST$도 좋은 문자열이다.

좋은 문자열 $A$와 $B$가 주어진다. 인접한 두 문자를 서로 바꾸는 연산만 써서 $A$를 $B$로 바꾸려고 한다. 바꾸는 도중에 나타나는 문자열도 모두 좋은 문자열이어야 한다. 필요한 연산의 최소 횟수를 구하는 프로그램을 작성하시오.

예를 들어 $A$가 aabbabab이고 $B$가 aaaabbbb이면 다섯 번의 연산으로 $A$를 $B$로 바꿀 수 있다. 대괄호는 그 단계에서 서로 바꾸는 두 문자이다.

aabba[ba]b → aab[ba]abb → aaba[ba]bb → aa[ba]abbb → aaa[ba]bbb → aaaabbbb

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

이어서 각 테스트 케이스마다 한 줄에 문자열 $A$와 $B$가 공백으로 구분되어 주어진다. $A$와 $B$는 좋은 문자열이고, 길이는 각각 2 이상 100,000 이하이다.

각 테스트 케이스마다 $A$를 $B$로 바꾸는 데 필요한 연산의 최소 횟수를 한 줄에 하나씩 출력한다. 바꿀 수 없으면 -1을 출력한다.