Problema A - Transformando Palabras
Rafael distruta numerosas clases de juegos con palabras. Actualmente, él está sumamente interesado en los juegos de transformación de palabras. Esencialmente, dada una palabra (una secuencia consecutiva de caracteres), debe aplicar un conjunto de reglas que especifican cómo debería ser cambiado cada caracter. En particular, está muy interesado en un juego donde sólo se utilizan tres letras ('A', 'B' y 'C'). El conjunto de reglas a aplicar es el siguiente:
A -> AB
B -> AC
C -> A

Esto significa que dada una palabra, todas las apariciones del caracter 'A' deberían ser transformadas en 'AB', todas las apariciones de 'B' deberían ser transformadas en 'AC' y todas las apariciones de 'C'deberían ser transformadas en 'A'. Por ejemplo, la palabra 'BCA' se transformaría en 'ACAAB':

Ahora Rafael considera una secuencia de palabras Si donde cada palabra se obtiene aplicándole las reglas ya definidas a la palabra anterior de la secuencia. La primera palabra de la secuencia, S1, es 'A'. Aplicando las reglas, S2 es 'AB', S3 es 'ABAC', S4 es 'ABACABA' y así siguiendo. La figura a continuación ilustra las transformaciones para estas primeras 4 palabras de la secuencia:

Rafael pensó que la secuencia que obtuvo era realmente bella y no pudo contenerse de calcular más y más palabras de la secuencia. Pero las palabras se hicieron tan largas que se volvió muy difícil hacerlo todo a mano, y necesita ayuda. Él se dio cuenta de que lo que necesita es una manera de calcular cuál es el K-ésimo caracter en la N-ésima palabra de la secuencia. Por ejemplo, si N es 4 y K es 3, la respuesta que está buscando es 'A', pues el 3er caracter de la 4ta palabra en la secuencia (S4='ABACABA') es 'A'. Si ambos N y K fueran 4, la respuesta sería 'C', ya que el 4to caracter de S4 es 'C'.
Debes ayudar a Rafael en estos cálculos.
El Problema
Dado un conjunto de enteros N y K, debes calcular cuál es el K-ésimo caracter de la N-ésima palabra en la secuencia definida anteriormente, esto es, el caracter en la posición K de la palabra SN. Notar que S1es siempre 'A' y el conjunto de reglas para transformar una palabra es siempre A->AB, B->AC y C->A.
Datos de entrada
La primera línea contiene un único entero C indicando el número de casos de siguen a continuación.
Luego siguen C líneas, cada una de ellas describiendo cada caso de prueba. Cada línea contiene dos enteros N y K, separados por un único espacio, indicando que debes computar el K-ésimo caracter de la N-ésima palabra en la secuencia. Se garantiza que K corresponde a una posición válida, es decir, SN contiene al menos K caracteres.
Datos de salida
La salida debería tener exactamente C líneas, cada una con un único caracter conteniendo la respuesta a los respectivos casos, esto es, cuál es el caracter en la posición K de la palabra SN. Las respuestas deberían darse en el mismo orden que la entrada, es decir, la primera línea de la salida debería ser la respuesta al primer caso de prueba, y así siguiendo.
Restricciones
Los siguientes límites se garantizan para todos los casos de prueba que serán usados para evaluar tu programa:



1 ≤ C ≤ 10 000
     
Número de casos de prueba


1 ≤ N ≤ 70
     
Posición de la palabra en la secuencia


1 ≤ K ≤ 1018
     
Posición del caracter en la palabra (entra en un signed integer de 64 bits)



Nota acerca de la evaluación
Para el conjunto de casos de prueba que vale el 25% de los puntos, siempre ocurre que C≤100, N≤10 y K≤200.
Para el conjunto de los casos de prueba que vale el 50% de los puntos, siempre ocurre que N≤30 y K≤107.
Entrada ejemplo
10
4 3
4 4
2 1
2 2
3 4
5 11
5 8
10 30
8 25
7 20

Salida ejemplo
A
C
A
B
C
C
A
B
A
A