FaceX is a very popular social network, used by many people. Here, people connect with each other by following others, which can be described as a directed graph, where ~u~ follows ~v~ is equivalent to having an edge ~u \to v~.

V — a user in a network of ~n~ people — notices many suspicious activities, which reduce the quality of the network. V realizes that many of these activities look like spam and suspects that there is a bot-created account in the network. V believes that a bot account has the following characteristics:

• ~s~ follows all other ~n-1~ people (there exists an edge ~s \to v~ for every ~v \neq s~);

• nobody follows ~s~ (there exists no edge ~u \to s~ for any ~u~).

Currently, V does not know the structure of the network, so V wants to use the system to perform queries in order to identify the bot account. In each query, V can ask whether ~u~ follows ~v~. However, due to system limits, V can perform at most ~3n~ queries. Help V find the bot account, or point out that the bot account does not exist in the system.

Interaction

First, you need to read an integer ~t~ (~1 \le t \le 1000~) — the number of test cases. For each test case, the interaction proceeds as follows:

• First, read an integer ~n~ (~2 \le n \le 10^4~) — the number of accounts in the network.

• To ask whether ~u~ follows ~v~ or not, print ? ~u~ ~v~ (~1 \le u, v \le n~; ~u \neq v~), then read the response:

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

  • False! — ~u~ does not follow ~v~.

• Once you have determined the bot account (or concluded that it does not exist), print ! ~s~ where ~s~ is the bot account (~1 \le s \le n~), or ! FRIENDLY if there is no bot account.

The judge of this problem is adaptive, meaning that the graph structure is not fixed and may be changed throughout the interaction, but it will remain consistent with the answers to the queries you have made so far.

For the answer to be considered correct, in addition to giving the answer within ~3n~ queries, you must ensure that the answer is correct for every graph consistent with the queries you have made.

It is guaranteed that the sum of ~n~ over all test cases does not exceed ~10^4~.

After printing a command, do not forget to print a newline and flush the standard output. To do this, you can use:

• fflush(stdout) or cout.flush() in C++;

• System.out.flush() in Java;

• flush(output) in Pascal;

• stdout.flush() in Python;

• see the standard documentation for other languages.

Scoring

The total score for this problem is ~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

In the first example, the network consists of 2 accounts. Both accounts follow each other, so there is no bot account.

In the second example, the network consists of 3 accounts. The first account follows both of the other accounts, but the other two accounts do not follow the first account. Thus, the first account is the bot account.