Vào ngày 07/09/2026, nqson và kinatraa - Hà Kiên cùng tốt nghiệp đại học. Vì Sơn đạt loại Xuất sắc nên được vinh danh trong buổi lễ riêng vào buổi sáng, còn Kiên tốt nghiệp loại Giỏi nên dự lễ vào buổi chiều. Không phục kết quả này, Hà Kiên đã thách đấu anh Sơn một trò chơi trí tuệ để phân tài cao thấp:

• Hai người lần lượt chọn một số nguyên chưa từng được ai chọn trong tập hợp các số từ 1 đến 9.
• Sơn là người đi trước.
• Nếu tại bất kỳ thời điểm nào, một người sở hữu 3 số bất kỳ có tổng đúng bằng \(15\), người đó sẽ lập tức giành chiến thắng. Nếu chọn hết cả \(9\) số mà không ai có bộ ba số nào tổng bằng \(15\), ván đấu kết thúc với kết quả hòa.

Thật may mắn, Sơn đã biết trò chơi này thực chất đẳng cấu (tương đương 100%) với trò chơi Tic-Tac-Toe (Cờ ca-rô 3×3) thông qua một Ma phương bậc 3 (Magic Square 3×3) có tổng mỗi hàng, cột và đường chéo đều bằng 15. Quá trình xây dựng ma phương như sau:

Bước 1: Đặt số 5 vào trung tâm, vì 5 tham gia vào nhiều bộ ba có tổng bằng 15 nhất (4 bộ: đi qua 1 hàng, 1 cột, 2 đường chéo):

| . | . | . |
| . | 5 | . |
| . | . | . |

Bước 2: Số 1 chỉ tham gia vào đúng 2 bộ ba (\(1+5+9=15\) và \(1+6+8=15\)), nên số 1 bắt buộc phải nằm ở ô cạnh (ô mép). Đối diện với 1 qua tâm 5 bắt buộc là 9:

| . | 1 | . |
| . | 5 | . |
| . | 9 | . |

Bước 3: Hai góc kề với 1 phải là 6 và 8 để tạo thành bộ \(1+6+8=15\):

| 8 | 1 | 6 |
| . | 5 | . |
| . | 9 | . |

Bước 4: Điền các số còn lại sao cho mỗi hàng, mỗi cột và 2 đường chéo đều có tổng bằng 15. Ta thu được ma phương chuẩn:

| 8 | 1 | 6 |
| 3 | 5 | 7 |
| 4 | 9 | 2 |

Theo quy tắc ma phương trên, vị trí các số được chia làm 3 nhóm:

• Ô tâm (Center): \(\{5\}\)
• Ô góc (Corner): \(\{2, 4, 6, 8\}\)
• Ô cạnh (Edge): \(\{1, 3, 7, 9\}\)

Trong lý thuyết trò chơi Tic-Tac-Toe, nếu cả hai người chơi đều đánh tối ưu ở các nước tiếp theo:

• Trường hợp 1 (Sơn đánh ô Góc):
  • Kiên chỉ có thể thủ hòa nếu đi ngay vào ô Tâm.
  • Nếu Kiên đi vào bất kỳ ô Cạnh nào hoặc bất kỳ ô Góc nào khác, Sơn luôn có chiến thuật ép thắng.

• Trường hợp 2 (Sơn đánh ô Tâm):
  • Kiên chỉ có thể thủ hòa nếu đi vào một trong bốn ô Góc.
  • Nếu Kiên đi vào một ô Cạnh, Sơn luôn ép thắng.

• Trường hợp 3 (Sơn đánh ô Cạnh):
  • Kiên chỉ có thể thủ hòa nếu đi vào ô Tâm, ô Cạnh đối diện, hoặc một trong hai ô Góc kề với cạnh đối diện.

Sơn và Kiên sẽ đấu với nhau \(t\) ván. Ở mỗi ván, Sơn chọn số \(x\) ở nước đầu tiên và Kiên chọn số \(y\) ở nước thứ hai (\(x \ne y\)). Sau 2 nước đi đầu này, cả hai đều thi đấu hoàn toàn tối ưu. Hãy xác định ai sẽ giành chiến thắng (nếu ván đấu hòa thì tính là Kiên thắng vì Kiên đã chặn đứng được Sơn).

Đầu vào

• Dòng đầu tiên chứa số nguyên dương \(T\) (\(1 \le T \le 100\)) — số lượng ván đấu.
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x\) và \(y\) (\(1 \le x, y \le 9\), \(x \ne y\)) lần lượt là nước đi đầu tiên của Sơn và Kiên.

Đầu ra

• Với mỗi ván đấu, in ra trên một dòng nqson nếu Sơn giành chiến thắng, hoặc in ra hakien nếu ván đấu hòa hoặc Kiên thắng.

Giới hạn

• \(1 \le T \le 100\)
• \(1 \le x, y \le 9\) và \(x \ne y\)

Ví dụ

Đầu vào:

3
8 5
8 1
5 2

Đầu ra:

hakien
nqson
hakien

Giải thích:

• Ván 1: Sơn đi góc \(8\), Kiên đi đúng vào tâm \(5\). Sau đó cả hai đánh chuẩn xác thì ván đấu hòa \(\rightarrow\) In ra hakien.
• Ván 2: Sơn đi góc \(8\), Kiên đi vào cạnh \(1\) (nước đi sai lầm). Sơn sẽ tận dụng để ép thắng \(\rightarrow\) In ra nqson.
• Ván 3: Sơn đi tâm \(5\), Kiên đi vào góc \(2\) (nước đi chuẩn xác để thủ hòa). Ván đấu kết thúc hòa \(\rightarrow\) In ra hakien.