FaceX là một mạng xã hội rất phổ biến, được nhiều người sử dụng. Tại đây, mọi người kết nối với nhau bằng cách theo dõi (follow) người khác, có thể mô tả như một đồ thị có hướng, trong đó ~u~ follow ~v~ tương đương với có cạnh ~u \to v~.

V — một người dùng trong mạng lưới gồm ~n~ người — nhận thấy có nhiều hoạt động đáng ngờ, làm giảm chất lượng của mạng. V nhận ra rằng nhiều hoạt động này có dấu hiệu spam và nghi ngờ có tài khoản được tạo bởi bot tồn tại trong mạng của mình. V cho rằng một tài khoản bot có các đặc điểm sau:

• ~s~ follow tất cả ~n-1~ người còn lại (tồn tại cạnh ~s \to v~ với mọi ~v \neq s~);

• không ai follow ~s~ (không tồn tại cạnh ~u \to s~ với bất kỳ ~u~ nào).

Hiện tại, V không biết cấu trúc của mạng, nên V muốn dựa vào hệ thống để thực hiện các truy vấn nhằm xác định tài khoản bot. Trong mỗi truy vấn, V có thể hỏi xem ~u~ có follow ~v~ hay không. Tuy nhiên, do giới hạn hệ thống, V chỉ có thể thực hiện tối đa ~3n~ truy vấn. Hãy giúp V tìm ra tài khoản bot, hoặc chỉ ra rằng trong hệ thống không có tài khoản bot nào.

Interaction

Đầu tiên, bạn cần đọc số nguyên ~t~ (~1 \le t \le 1000~) — số lượng test case. Với mỗi test case, quá trình tương tác diễn ra như sau:

• Đầu tiên, đọc số nguyên ~n~ (~2 \le n \le 10^4~) — số tài khoản trong mạng.

• Để hỏi xem ~u~ có follow ~v~ hay không, in ra ? ~u~ ~v~ (~1 \le u, v \le n~; ~u \neq v~), sau đó đọc phản hồi:

  • True! — ~u~ follow ~v~;

  • False! — ~u~ không follow ~v~.

• Khi đã xác định được tài khoản bot (hoặc kết luận không tồn tại), in ra ! ~s~ trong đó ~s~ là tài khoản bot (~1 \le s \le n~), hoặc ! FRIENDLY nếu không tồn tại tài khoản bot.

Hệ thống chấm của bài này adaptive, tức là cấu trúc đồ thị không cố định và có thể được thay đổi xuyên suốt quá trình tương tác, nhưng sẽ nhất quán với các câu trả lời của các truy vấn trước đó của thí sinh.

Để đáp án được xét là đúng, ngoài việc đưa ra được đáp án trong ~3n~ truy vấn, bạn cần đảm bảo rằng đáp án phải đúng với mọi đồ thị nhất quán với các truy vấn bạn đã đưa ra.

Dữ liệu đảm bảo rằng tổng ~n~ qua các test case không được vượt quá ~10^4~.

Sau khi in một lệnh, đừng quên in dấu xuống dòng và flush đầu ra chuẩn. Để làm điều này, bạn có thể sử dụng:

• fflush(stdout) hoặc cout.flush() trong C++;

• System.out.flush() trong Java;

• flush(output) trong Pascal;

• stdout.flush() trong Python;

• xem tài liệu chuẩn cho các ngôn ngữ khác.

Scoring

Tổng điểm cho bài này là ~1500~.

Sample Input 1

2
2

True!

True!

3

True!

False!

True!

False!

True!

True!

Sample Output 1

? 1 2

? 2 1

! FRIENDLY

? 1 2

? 2 1

? 1 3

? 3 1

? 2 3

? 3 2

! 1

Notes

Trong ví dụ đầu tiên, mạng gồm có 2 tài khoản. Cả 2 tài khoản đều follow nhau, do đó không có tài khoản bot nào cả.

Trong ví dụ thứ hai, mạng gồm có 3 tài khoản. Tài khoản đầu tiên theo dõi cả hai tài khoản còn lại, nhưng hai tài khoản còn lại không theo dõi tài khoản thứ nhất. Như vậy, tài khoản thứ nhất là tài khoản bot.