DNA 복사

상근이는 졸업 프로젝트로 DNA 복사를 시뮬레이션하기로 했다.

DNA 문자열은 알파벳 A, C, G, T로만 이루어져 있다. 원본 문자열 $S$가 주어졌을 때, 목표 문자열 $T$를 만드는 데 필요한 최소 복사 횟수를 구하자.

한 번의 복사는 다음 규칙을 따른다.

• 복사할 문자열은 $S$의 연속된 일부이거나, 지금까지 만들어 둔 $T$의 연속된 일부여야 한다.
• 복사할 때 문자열을 뒤집어서 붙여도 된다.
• 복사한 문자열은 $T$의 연속된 한 구간을 채우며, 모든 구간이 채워지면 $T$가 완성된다.

즉, 완성된 $T$의 각 위치는 정확히 한 번의 복사로 채워지고, $S$에서 복사하거나 이미 채워 둔 부분에서 복사할 수 있다(뒤집기 허용). 채우는 순서는 자유이며, 어떤 부분을 복사원으로 쓰려면 그 부분이 복사 시점에 이미 완성되어 있어야 한다.

예를 들어 $S =$ ACTG, $T =$ GTACAATTAAT인 경우 다음과 같이 $5$번 만에 만들 수 있다.

1. $S$에서 TG를 복사한 뒤 뒤집어 GT로 붙인다 → GT.........
2. $S$에서 AC를 복사해 붙인다 → GTAC.......
3. 이미 만든 부분에 있는 TA를 복사해 붙인다 → GTAC...TA..
4. TA를 복사한 뒤 뒤집어 AT로 붙인다 → GTAC...TAAT
5. 이미 만든 부분에 있는 AAT를 복사해 붙인다 → GTACAATTAAT

첫째 줄에 테스트 케이스의 개수 $t$가 주어진다($1 \le t \le 100$). 각 테스트 케이스는 두 줄로 이루어지며, 첫 줄에 문자열 $S$, 둘째 줄에 문자열 $T$가 주어진다. 두 문자열은 알파벳 A, C, G, T로만 이루어지고 길이는 $1$ 이상 $18$ 이하이다.

각 테스트 케이스마다 $T$를 만드는 데 필요한 최소 복사 횟수를 한 줄에 출력한다. 만들 수 없으면 impossible을 출력한다.