헥토르의 시험 답안

헥토르는 각 문제에 네 개의 보기(A, B, C, D)가 있는 객관식 시험을 좋아합니다. 정답을 모를 때는 아무렇게나 찍는 대신 다음 규칙에 따라 답을 표시합니다.

1. 첫 번째 문제에는 A를 적습니다.
2. 두 번째 문제에는 바로 앞에서 고른 글자의 '다음 글자'를 적습니다. (B)
3. 세 번째 문제에는 바로 앞에서 고른 글자의 '다음 글자'를 적습니다. (C)
4. 네 번째 문제에는 바로 앞에서 고른 글자보다 '한 글자 작은' 글자를 적습니다. (B)

그 뒤로는 시험이 끝날 때까지 2, 3, 4번 규칙을 순서대로 반복합니다. (물론 괄호 안의 실제 글자는 매번 달라집니다.)

'다음 글자' 규칙:

• A의 다음 글자는 B
• B의 다음 글자는 C
• C의 다음 글자는 D
• D의 다음 글자는 A

'한 글자 작은' 규칙:

• A보다 한 글자 작은 글자는 D
• B보다 한 글자 작은 글자는 A
• C보다 한 글자 작은 글자는 B
• D보다 한 글자 작은 글자는 C

따라서 처음 12개 문제에 대해 헥토르는 순서대로 ABCBCDCDADAB라고 답합니다.

헥토르가 $N$번째 문제에 어떻게 답할지 구하세요.

첫째 줄에 테스트 케이스의 개수 $Z$가 주어집니다. ($1 \le Z \le 10$)

이어지는 $Z$개의 줄에는 각 줄마다 정수 $N$이 하나씩 주어집니다. ($1 \le N \le 10^9$)

각 테스트 케이스마다 헥토르가 $N$번째 문제에 답한 글자를 한 줄에 하나씩 출력하세요.