칩 더미 셔플

포커 칩 두 더미 S1, S2가 있다. 각 더미에는 정확히 C개의 칩이 있으며, 칩의 색은 여러 종류일 수 있다. 문자열은 항상 아래쪽 칩부터 위쪽 칩 순서로 적는다.

한 번의 셔플은 두 더미를 번갈아 끼워 넣어 길이 2*C인 새 더미 S12를 만드는 과정이다. S12의 맨 아래 칩은 S2의 맨 아래 칩이고, 그 위에는 S1의 맨 아래 칩이 놓인다. 그다음에는 S2의 아래에서 두 번째 칩, S1의 아래에서 두 번째 칩이 차례로 놓이며, 마지막에는 S1의 맨 위 칩이 S12의 맨 위에 놓인다.

셔플이 끝나면 S12의 아래쪽 C개 칩이 새 S1이 되고, 위쪽 C개 칩이 새 S2가 된다. 이후 같은 셔플을 반복할 수 있다.

각 데이터셋마다, 목표 더미가 몇 번의 셔플 후 만들어지는지 구하라. 목표와의 비교는 셔플로 S12를 만든 직후에 한다.

첫 줄에는 데이터셋의 개수 N이 주어진다. (1 <= N <= 1000)

각 데이터셋은 네 줄로 이루어진다.

1. 한 더미에 들어 있는 칩의 수 C (1 <= C <= 100)
2. 초기 S1의 칩 색을 아래쪽부터 나타낸 길이 C의 문자열
3. 초기 S2의 칩 색을 아래쪽부터 나타낸 길이 C의 문자열
4. 목표 더미의 칩 색을 아래쪽부터 나타낸 길이 2*C의 문자열

칩 색은 A부터 H까지의 대문자 한 글자이며, 문자열 사이에는 공백이나 구분자가 없다.

각 데이터셋마다 목표 더미를 만들기 위해 필요한 최소 셔플 횟수를 한 줄에 출력한다. 목표 더미에 도달할 수 없으면 -1을 출력한다.