시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 667 299 218 46.983%

문제

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

  1. ab 는 좋은 문자열이다.
  2. 만약 문자열 [S]가 좋은 문자열이라면, 오른쪽과 왼쪽 끝에 각각 a와 b를 추가한 문자열 a[S]b 또한 좋은 문자열이다.
  3. 만약 문자열 [S]와 [T]가 좋은 문자열이라면 이들을 붙여 쓴 [S][T] 또한 좋은 문자열이다.

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

예를 들어, A = aabbabab 이고 B = aaaabbbb라 해 보자. 그렇다면 다음과 같이 5번의 연산을 통해 A를 B로 변환할 수 있다.

aabbabab → aabbaabb → aabababb → aabaabbb → aaababbb → aaaabbbb

입력

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

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

출력

T줄에 걸쳐서, 각 테스트 케이스에서 주어진 문자열 A를 문자열 B로 변환할 때 필요한 연산의 수를 출력하시오.

만약 변환이 불가능한 경우 -1을 출력한다.

예제 입력

2
aabbabab aaaabbbb
aabbab abaabb

예제 출력

5
2

힌트

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2014 H번