XYZ String

An "XYZ string" is built step by step using only the three characters X, Y, and Z.

1. The stage 1 string is X.
2. Each later stage is made by replacing every character of the previous stage at the same time, using these rules.
   • X becomes YZ.
   • Y becomes Z.
   • Z becomes X.

The first six stages are as follows.

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

For the stage N XYZ string, write a program that answers one of the following three queries.

1. Find the length of the stage N string.
2. Find the k-th character of the stage N string.
3. Count how many times a given character, one of X, Y, or Z, appears in the stage N string.

The first line contains the query type, one of 1, 2, or 3.

The second line contains an integer N (1 <= N <= 100).

If the query type is 2, the third line contains an integer k. The value of k is always at most the length of the stage N string.

If the query type is 3, the third line contains one character: X, Y, or Z.

For query type 1, print the length of the string.

For query type 2, print the k-th character.

For query type 3, print the number of occurrences of the given character.