Let’s play a game. You are given a row of n balls, each ball is either black or white. Their positions in a row are numbered from 1 to n. You know the total number of balls n, but have no information about the order of their colors. You don’t even know how many white balls are there.

You are allowed to make queries v u (1 ≤ v, u ≤ n). If the ball on position v is black and the ball on position u is white, then these two balls are swapped. Otherwise, nothing happens. Even if the balls are swapped, you don’t get any feedback.

After a number of queries (can be zero) you a required to make a "statement." "Statement" also consists of two positions v, u. Your goal is to choose positions, that contain two balls of the same color.

In this problem we ask you to print both queries and a "statement", that comes after them.

A single test can contain several games. Furthermore, all tests except the first one contain 99 game descriptions. In the first game n = 2, in the second — n = 3 ... in the last game n = 100.

First test is the same as the sample below.

In all other tests your program must make the right statement at least in 80 games.

Note, that we do not guarantee that the tests are random.

First line contains m — number of games in the test. For every test, except for the first one, m=99.

Remaining lines contain ciphered (except for the first test) order of balls in the row. Thus we guarantee, that the tests are determined beforehand and do not depend on your strategy. Please, do not try to use this data in any way and do not try to decipher it.

Output m game descriptions.

One description consists of (k+1) lines, where k — number of queries made by your program.

First k lines should contain the queries in the following format: ? v u (1 ≤ v, u ≤ n, v ≠ u).

The last line should contain the "statement": ! v u (1 ≤ v, u ≤ n, v ≠ u).

Total amount of lines (over all games in a test) should not exceed 5 · 10⁵.

In the sample test white balls are marked as 0, black ones — as 1. Let’s examine the sample closely.

First game: 01 → 01 → 10 → 01 — we did not guess correctly.

Second game: 101 → 011 → 110 — we guessed correctly.

In this test we have guessed correctly in one game out of two.