시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 52 22 17 41.463%

문제

리트는 알파벳을 다른 기호로 바꿔서 적는 방법으로, 주로 인터넷에서 사용한다. 영어 알파벳의 각 문자는 비슷하게 생긴 하나 또는 그 이상의 문자로 바꿔서 적는다. 예를 들어, ACMICPC에서 A를 4, C를 (, M을 |V|, I를 1, P를 |>로 바꾸면, "4(IVI1(|>(" 로 적을 수 있다. M과 P의 경우처럼 한 알파벳을 길이가 1보다 큰 문자로 바꿀 수도 있다.

한 알파벳을 다른 문자로 바꾸는 방법이 여러 가지일 수도 있다. 예를 들어, D를 나타낼 때 [), |), |> 를 사용할 수 있다. 이러한 점들 때문에, Leet는 매우 읽기 어렵다.

영어 알파벳으로 적혀있는 원래 단어와 리트로 적혀진 단어가 주어졌을 때, 두 단어가 아래 조건을 지키는지 아닌지를 검사하는 프로그램을 작성하시오.

  1. 각 알파벳을 리트로 나타낼 때, 최대 k개의 문자로 바꿀 수 있다. k는 입력으로 주어진다.
  2. 한 알파벳을 리트로 바꾸는 방법은 한 가지이다. 예를 들어, D의 리트로 [)를 사용하는 경우에는 |>를 D의 리트로 사용할 수 없다.
  3. 두 개 또는 그 이상의 알파벳을 리트로 바꿨을 때, 그 결과가 같을 수도 있다. 예를 들어, D와 P의 리트가 동시에 |>일 수도 있다.
  4. 알파벳과 리트가 서로 비슷하게 보이지 않아도 상관없다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 한 알파벳을 리트로 바꿨을 때 리트의 최대 길이 k가 주어진다. (1 ≤ k ≤ 3) 둘째 줄에는 원래 단어가 주어진다. 단어는 알파벳 소문자 a-z로만 이루어져 있고, 길이는 1보다 크거나 같고, 15보다 작거나 같다. 셋째 줄에는 리트로 나타낸 단어가 주어진다. 리트의 길이는 1보다 크거나 같으며, a-z, A-Z, 0-9, @, \, /, -, =, ^, |, [, ], (, ), {, }, <, >로 이루어져 있다.

출력

각 테스트 케이스마다, 입력으로 주어진 단어가 같으면 1, 아니면 0을 출력한다.

예제 입력

2
3
mississippi
nni55i55ippi
2
foobar
|=o08ar

예제 출력

1
0

힌트

출처

ACM-ICPC > Regionals > Asia > Korea > Asia Regional - Daejeon 2011 F번