Lihwy và FireGhost là hai đá thủ nổi tiếng trong cộng đồng VNOI. Để cạnh tranh danh hiệu "vua đá", Lihwy đã đề xuất FireGhost cùng chơi một trò chơi:
Có ~n~ viên đá, hai người chơi sẽ lần lượt thực hiện các thao tác sau (Lihwy đi trước):
- Nếu số viên đá còn lại là ~x~, người chơi hiện tại phải bốc ra ngoài ~k \ge 1~ viên đá sao cho ~\gcd(k, x) = 1~.
Ai là người bốc viên đá cuối cùng ra ngoài sẽ thắng. Nếu cả hai chơi hợp lý, ai sẽ là người thắng?
Input
Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 100~) — số testcase của bài toán.
Dòng thứ ~i~ trong ~t~ dòng tiếp theo chứa số nguyên dương ~n~ (~1 \le n \le 10^9~) thể hiện một testcase — số viên đá ban đầu trong trò chơi.
Output
Với mỗi testcase, in ra Lihwy hoặc FireGhost (không quan trọng kí tự in hoa hay thường) tương ứng với người thắng trò chơi.
Scoring
Subtask | Điểm | Giới hạn |
---|---|---|
1 | ~25~ | tổng của ~n~ trong tất cả các testcase không vượt quá ~5000~ |
2 | ~75~ | không có giới hạn gì thêm |
Sample Input 1
2
1
2
Sample Output 1
Lihwy
FireGhost
Notes
Ở test ví dụ đầu tiên, Lihwy chỉ cần bốc ~1~ viên đá và chiến thắng.
Ở test ví dụ thứ hai, Lihwy chỉ có một lựa chọn duy nhất là bốc ~1~ viên đá, còn FireGhost sẽ bốc viên đá còn lại ở lượt chơi tiếp theo và chiến thắng.
Comments
gcd là j v =))?
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
This comment is hidden due to too much negative feedback. Show it anyway.
:hqv: