Your friend has a randomly-generated directed graph of ~N~ nodes. This is a special graph. Each node will have an outdegree of at most one. That is, there will be at most one edge going out from each node. He does not want to tell you the graph, but will allow you to ask ~Q~ questions of the form:

• ? a b Is ~a~ a descendant of ~b~? That is, is there a path that allows for you to travel from ~b~ to ~a~? If ~1 \le a, b \le N, a \neq b~, then your friend will tell you 1 for "Yes" and 0 for "No". Otherwise, your friend will give you -1 and continue on to the next question.

After ~Q~ questions, your friend will simply stop responding.

Your goal is to surprise your friend by telling him the number of cycles in the graph. A cycle is a path that visits not less than two nodes, uses each edge at most once, and returns to the starting node. For example ~1 \to 2 \to 3 \to 1~ is a cycle, while ~1~ is not. Each node can only be used in one cycle.

When you have the answer, surprise your friend by output ! k, where ~k~ is the number of cycles. Afterwards, your friend will stop responding, and your program must exit.

The algorithm that your friend used to generate the graph is described below:

# N is the number of nodes in the graph
def generate_graph(N):
    # for x between 1 and N, inclusive:
    for x in range(1, N+1):
        # u = random number between 1 and N
        u = randint(1, N)
        if u != x:
            # add a directed edge from x to u
            directed_edge_to[x] = u
        else:
            # outdegree of 0
            directed_edge_to[x] = -1

Interaction

The first line will contain the integer ~N~ ~(1 \le N \le 5000)~.

Afterwards, you must start asking questions.

To ask a question, output ? a b, which asks whether ~a~ is a descendant of ~b~. You will receive a 1 for a "Yes" and 0 for "No". If you receive a -1, that means ~a~ and ~b~ were invalid, and your friend will simply continue on to the next question. They will, however, count this as a question.

Once you have the answer (the number of cycles), output ! k, where ~k~ is the number of cycles. Your friend will stop responding, and you must exit. Note that printing the answer does not count as question.

Note: after each output, you may need to flush your output for your friend to receive it. Please search up how to flush in the language that you are using.
Note 2: your friend may take up to ~2~ seconds of the time limit.

Other Constraints

~Q = \bigg\lceil \frac{K}{4} \times N \bigg\rceil~, where ~K = 30~.

Sample Interaction

The given graph is:

The only cycle in this graph is ~2 \to 3 \to 4 \to 2~.

>>> denotes your output, and <<< denotes your friend's output.

<<< 4
>>> ? 2 1
<<< 1
>>> ? 4 2
<<< 1
>>> ? 2 4
<<< 1
>>> ? 1 3
<<< 0
>>> ? 3 2
<<< 1
>>> ! 1