공정한 문자열

Alice는 문자열을 생성하는 기계를 만든다. 기계에는 1부터 $N$까지 번호가 붙은 상태가 $N$개 있고, 상태 사이에는 방향이 있는 간선이 있다. 각 간선에는 고정된 문자 집합의 문자 하나가 붙어 있다. 상태 중 일부는 최종 상태이다. 기계는 상태 1에서 출발해 최종 상태에서 끝나는 경로를 따라가며, 지나간 간선의 문자를 순서대로 이어 붙여 문자열을 만든다. 경로는 같은 상태나 같은 간선을 여러 번 지날 수 있다. 최종 상태를 지난 뒤 다시 최종 상태에서 끝나는 것도 가능하다. 자기 자신으로 향하는 간선도 허용되고, 같은 문자로 표시된 간선이 같은 두 상태를 두 개 이상 잇는 것도 허용된다.

Bob이 좋아하는 문자열은 $S$이고, Carol이 좋아하는 문자열은 $T$이다. Alice는 부분 문자열로 나타나는 $S$의 출현 횟수와 $T$의 출현 횟수가 같은 문자열만 정확히 생성하는 기계를 만들 수 있는지 알고 싶다. 그런 문자열은 모두 생성하고, 그 밖의 문자열은 하나도 생성하지 않아야 한다. 출현은 서로 겹칠 수 있다. 예를 들어 banana에는 ana가 두 번 나타난다.

그림 H.1은 입력의 첫 번째 테스트 케이스에 해당하는 기계를 보여준다. 정사각형 상태가 최종 상태이다.

첫 줄에 테스트 케이스의 수 $K$ ($1\leq K \leq 50$)가 주어진다. 이어지는 $K$개의 줄에는 각각 세 문자열 $A$, $S$, $T$가 주어진다. $A$는 기계에서 쓸 수 있는 고정된 문자 집합이며, 서로 다른 영문 소문자로 이루어진다. $S$는 Bob의 문자열이고, $T$는 Carol의 문자열이다. 길이는 $1\leq |S|,|T|\leq 500$을 만족한다. $S$와 $T$에 나타나는 문자는 모두 $A$에 포함된다.

각 테스트 케이스마다 그런 기계를 만들 수 있으면 1, 없으면 0을 한 줄에 출력한다.