알사탕 2

당신은 이전 단계에서 친구와 알사탕을 나눠먹는 문제를 풀어본 적이 있다. 기억을 돕기 위해서 문제를 다시 설명하면, 당신은 친구 한 명과 같이 $N$개의 알사탕을 나누어 먹는다. 알사탕은 모두 $N$개가 있는데, 각각의 알사탕의 중간에는 구멍이 뚫려 있고, 이 구멍을 하나의 줄이 지나고 있어서 모든 알사탕은 하나로 이어져 있다. 줄을 끊지 않고는 중간에 있는 알사탕을 먼저 먹을 수 없기 때문에, 먹을 수 있는 알사탕은 줄의 양쪽 끝에 놓인 두 개이다. 당신이 먼저 하나를 먹으면 당신의 친구가 다시 하나를 먹는 식으로 알사탕을 먹는다. 따라서, $N$이 짝수라면 당신과 당신 친구 모두 $N/2$개의 알사탕을 먹고, $N$이 홀수라면 당신은 $(N+1)/2$개, 당신의 친구는 $(N-1)/2$개의 알사탕을 먹는다. 알사탕은 총 $26$가지가 있고, a부터 z까지의 문자로 각 종류에 해당하는 알사탕을 표현할 수 있다.

이전에 풀었던 문제는 여러분이 알사탕을 먹을 수 있는 방법 하나를 출력하는 문제였다. 이제 여러분은 반대로, 알사탕들이 주어지고, 알사탕을 먹을 수 있는 방법이 추가로 주어졌을 때, 과연 저 순서대로 알사탕을 먹는 것이 가능한 지 검증 하는 프로그램을 작성해야 한다.

이전에 사용한 다음과 같이 알사탕이 놓여진 경우를 생각해보자. $N=6$이다.

당신이 $1$번을 먹은 뒤 친구가 $2$번을 먹고, 다시 당신이 $6$번을 먹은 뒤 친구가 $5$번을 먹었다고 하자. 마지막으로 당신이 $4$번을 먹고 친구가 $3$번을 먹으면 최종적으로 당신이 먹은 사탕을 순서대로 나타낸 문자열은 adb이며, 친구가 먹은 사탕을 순서대로 나타낸 문자열은 bac이다. 따라서, abcbad로 사탕이 놓여졌을 때 당신이 adb의 순서로 사탕을 먹을 수 있는지 물어보았다면 답은 참이 되어야 하며, 당신이 cba의 순서로 사탕을 먹을 수 있는지 물어보았다면 답은 거짓이 되어야 한다. 왜냐하면 맨 처음에 먹을 수 있는 사탕은 a 아니면 d이기 때문이다.

알사탕의 수, 알사탕의 순서, 당신이 먹을 수 있다고 생각되는 알사탕의 순서가 주어졌을 때, 실제로 이 순서대로 알사탕을 먹는 것이 가능한지 여부를 알려주는 프로그램을 작성하시오.

입력 형식

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

각 케이스의 첫째 줄에 알사탕의 수를 나타내는 자연수 $N$ (1 이상 $10\,000$ 이하)가 주어진다. 다음줄에는 영어 소문자로 된 길이 $N$인 문자열이 주어지는데, 이 문자열은 왼쪽부터 오른쪽으로 알사탕이 꿰인 줄을 읽었을 때 각 위치에 놓인 알사탕을 나타내는 문자열이다. 그 다음줄에는 역시 영어 소문자로 된 문자열이 주어지는데, 이 문자열의 길이는 $N$이 짝수라면 $N/2$, $N$이 홀수라면 $(N+1)/2$이다. 이 문자열은 당신이 먹을 수 있다고 생각되는 알사탕의 순서이다.

모든 테스트케이스에 대한 알사탕의 수 $N$의 총합은 $2$만을 넘지 않는다.

출력 형식

각 줄마다 테스트케이스에 대한 결과를 차례대로 출력한다. 여기에는 주어진 알사탕들을 당신이 주어진 순서대로 먹을 수 있다면 1, 아니라면 0을 출력한다.

예제

2
6
abcbad
adb
6
abcbad
cba

1
0

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설