Для кодування двійкового рядка парної довжини в послідовність A, T, C та G ми виконуємо ітерацію зліва направо та замінюємо символи наступним чином:

• 00 замінюється на A
• 01 замінюється на T
• 10 замінюється на C
• 11 замінюється на G

Дано двійковий рядок ~S~ довжиною ~N~ ( ~N~ парне). Знайдіть утворену закодовану послідовність.

Обмеження

• ~1 \le T \le 10^2~
• ~2 \le N \le 10^3~
• ~N~ парне.
• ~S~ містить лише 0 та 1.

Input

Перший рядок містить ціле число ~T~ - кількість тестів. Кожен тест містить два рядки вхідних даних.

Перший рядок тесту містить одне ціле число ~N~ - довжину послідовності.

Другий рядок тесту містить двійкову послідовність ~S~.

Output

Для кожного тесту в окремому рядку вивести закодовану послідовність.

Sample Input 1

4
2
00
4
0011
6
101010
4
1001

Sample Output 1

A
AG
CCC
CT