시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 249 115 94 48.958%

문제

평소 도박을 즐겨하는 병규는 방학을 맞아, 한국 최대의 카지노 코스모스랜드를 찾았다. 일확천금의 꿈에 부풀어 여러 게임에 참여했지만, 입장 한 시간 만에 재산의 절반을 탕진하고 말았다.

평소 블랙잭에 자신이 있었던 병규는, 마지막 희망으로 블랙잭 테이블에 앉았다. 코스모스랜드에서는 일반 블랙잭과는 조금 다른 방식의 블랙잭인 "HY블랙잭" 이라는 게임을 만들어서 진행 중이었다. 규칙은 다음과 같다.

  • 딜러가 로또 기계에서 2 이상의 정수가 써진 공을 하나 뽑는다. 이때 나온 수가 K라면 딜러의 수는 K가 된다.
  • 플레이어는 딜러의 수 K를 확인하고, 카드를 받아 그 합이 정확히 K가 되도록 하면 게임에서 승리하게 된다.
  • 각 카드에는 정수가 쓰여 있다. 일반 트럼프카드와 달리 1 이상 K-1 이하의 정수가 한 번씩 쓰여 있고, 오름차순으로 정렬되어 있다. 플레이어는 연속된 몇 장의 카드만 골라서 받을 수 있다.
  • 만약 연속된 카드의 합으로 딜러의 수 K를 만들 수 없을 경우, 플레이어가 패배한다.

예를 들어, 딜러가 뽑은 공의 수가 9라면, 병규는 연속된 카드 2,3,4의 합으로 9를 만들 수 있으므로 병규의 승리가 된다. 하지만 딜러가 뽑은 공의 수가 4라면, 연속된 카드의 합으로 4를 만들 수 없으므로 병규의 패배가 된다.

K가 주어졌을 때, 병규가 이길 수 있는지 없는지 알려주는 프로그램을 작성하여 병규를 도와주자!

입력

첫번째 줄에, 테스트케이스의 수 N (1 ≤ N ≤ 103)이 주어진다. 그 다음 줄부터 N개의 줄에 테스트케이스가 한 줄에 하나씩 주어진다. 각 테스트케이스에는 딜러가 뽑은 공의 수 K (2 ≤ K ≤ 109)가 주어진다.

출력

각 경우마다 병규가 이길 수 있다면, "Gazua"를, 병규가 이길 수 있는 방법이 없다면 "GoHanGang"을 출력한다. (큰따옴표는 출력하지 않는다)

예제 입력 1

2
9
4

예제 출력 1

Gazua
GoHanGang