XYZ 문자열

"XYZ 문자열"은 문자 X, Y, Z로만 이루어지며, 다음 규칙으로 단계별로 만들어지는 문자열이다.

1. 1단계 문자열은 X이다.
2. 다음 단계의 문자열은 바로 이전 단계 문자열의 각 문자를 아래 규칙대로 동시에 바꾸어 만든다.
   • X는 YZ가 된다.
   • Y는 Z가 된다.
   • Z는 X가 된다.

처음 여섯 단계는 다음과 같다.

1. X
2. YZ
3. ZX
4. XYZ
5. YZZX
6. ZXXYZ

N단계의 XYZ 문자열에 대해 다음 세 질의 중 하나를 처리하는 프로그램을 작성하시오.

1. N단계 문자열의 길이를 구한다.
2. N단계 문자열의 k번째 문자를 구한다.
3. N단계 문자열에서 주어진 문자 X, Y, Z 중 하나가 몇 번 나타나는지 구한다.

첫째 줄에 질의 번호가 주어진다. 질의 번호는 1, 2, 3 중 하나이다.

둘째 줄에 정수 N (1 <= N <= 100)이 주어진다.

질의 번호가 2이면 셋째 줄에 정수 k가 주어진다. k는 항상 N단계 문자열의 길이 이하이다.

질의 번호가 3이면 셋째 줄에 문자 X, Y, Z 중 하나가 주어진다.

질의 번호가 1이면 문자열의 길이를 출력한다.

질의 번호가 2이면 k번째 문자를 출력한다.

질의 번호가 3이면 주어진 문자가 나타나는 횟수를 출력한다.