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

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.