Đây là bài A đề thi thử để test hệ thống của Olympic MTTN năm nay, không mang tính chất hardcore.

http://online.vku.udn.vn/contest/precentralolp2022b1

Hiếu là 1 học sinh chăm học của ĐTQG Đà Nẵng. Do quá mải mê học Geometric distribution (các bạn có thể tham khảo thuật toán tại đây) vì mục tiêu vòng 2 VOI mà Hiếu đã quên mất cuộc hẹn quan trọng với người yêu mình là Ân. Biết Hiếu là 1 học sinh chuyên Tin, tuy rất giận dữ nhưng Ân đã ra cho Hiếu 1 thử thách để anh chàng có cơ hội được giảng hòa. Cô ra cho Hiếu \(T\) (\(T \le 50\)) câu hỏi, mỗi câu hỏi là 1 số nguyên \(X\), Hiếu phải đếm xem số \(X (X \neq 0)\) có số lượng ước dương là 1 số chẵn hay lẽ.

Valentine sắp đến, là 1 người tham lam nên Hiếu vừa muốn được giảng hòa trong đêm Valentine trong khi mình vẫn có thể học Geometric distribution. Biết các bạn học sinh tham gia kỳ thi Olympic Miền Trung và Tây Nguyên rất giỏi nên anh ấy muốn nhờ các bạn giúp anh ấy vượt qua thử thách này để mình có thể có thêm thời gian học tập mà vẫn được giảng hòa. Các bạn hãy giúp Hiếu kiểm tra xem số \(X\) có số lượng ước dương là chẵn hay lẽ nhé!

Input

• Dòng đầu tiên chứa 1 số nguyên duơng \(T\) (\(T \le 50\)) là số câu hỏi Ân đặt ra cho Hiếu.
• \(T\) dòng tiếp theo, mỗi dòng là 1 số nguyên \(X\) (\(|X| \le 10^{18}, X \neq 0\)).

Output

• Gồm T dòng, mỗi dòng in ra GIANG nếu \(X\) là số có số lượng ước dương là chẵn, ngược lại in ra HOA.

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(|X| \le 10^6\).
• Subtask \(2\) (\(30\%\) số điểm): \(|X| \le 10^{12}\).

Example

3
1
6
109

HOA
GIANG
GIANG