#!/usr/bin/env python3

"""
Example usage:

First create an input file like "seatingplan.input0.txt".
Input file syntax:
```
T
N
g0 g1 ... g(N-1)
N
g0 g1 ... g(N-1)
...
```

For python programs, say "solution.py" (normally run as "pypy3 solution.py"):

    python3 testing_tool.py pypy3 solution.py < your_input_file

For C++ programs, first compile it
(e.g. with "g++ -g -O2 -std=gnu++20 -static solution.cpp -o solution.out")
and then run

    python3 testing_tool.py ./solution.out < your_input_file

"""

import subprocess
import sys

QUERY_LIMIT = 10000

def error(msg):
    print("ERROR:", msg)
    sys.exit(1)

def main():
    if len(sys.argv) < 2:
        print(f'Usage: python3 testing_tool.py program... < input.txt')
        sys.exit(0)

    try:
        T = int( input() )
    except Exception:
        error('Bad input format: first line must contain the number T of tests.')

    TESTS = []
    for test in range(1, T+1):
        try:
            N = int( input() )
        except Exception:
            error(f'Test {test}: Bad input format: first line of test must contain N.')

        try:
            G = [ int(_) for _ in input().split() ]
            assert len(G) == N
            assert list(sorted(G)) == list(range(N))
        except Exception:
            error(f'Test {test}: Bad input format: second line of test must contain the permutation g of numbers 0..N-1.')
        TESTS.append((N, G))

    proc = subprocess.Popen(sys.argv[1:], stdin=subprocess.PIPE, stdout=subprocess.PIPE)

    proc.stdin.write(f"{T}\n".encode("utf8"))
    proc.stdin.flush()
    print(f"< {T}")

    max_queries_used = 0

    for test in range(1, T+1):
        N, G = TESTS[test-1]
        S = [ None for _ in range(N) ]
        for n in range(N): S[G[n]] = n
        queries_used = 0

        proc.stdin.write(f"{N}\n".encode("utf8"))
        proc.stdin.flush()
        print(f"< {N}")

        while True:
            try:
                line = proc.stdout.readline().decode("utf8")
                line = line.strip()
            except Exception:
                error(f'Test {test}: Garbage in contestant\'s output.')

            print(f'> {line}')
            tokens = line.split()
            if not tokens:
                error(f'Test {test}: Got empty line, must be ? or !.')
            command, args = tokens[0], tokens[1:]

            if command not in ('?', '!'):
                error(f'Test {test}: Invalid command {command}, must be ? or !.')

            if command == '?':
                queries_used += 1
                if queries_used > QUERY_LIMIT:
                    error(f'Test {test}: Wrong answer: Too many queries.')

                try:
                    args = [ int(_) for _ in args ]
                    assert len(args) == 3
                    assert len(set(args)) == 3
                    assert all(0 <= x < N for x in args)
                except Exception:
                    error(f'Test {test}: Wrong answer: invalid query.')

                positions = [ S[x] for x in args ]
                answer = max(positions) - min(positions) + 1

                proc.stdin.write(f"{answer}\n".encode("utf8"))
                proc.stdin.flush()
                print(f"< {answer}")

            if command == '!':
                try:
                    args = [ int(_) for _ in args ]
                    assert len(args) == N
                    assert len(set(args)) == N
                    assert all(0 <= x < N for x in args)
                except Exception:
                    error(f'Test {test}: Wrong answer: not a valid permutation.')

                if args == G or args == list(reversed(G)):
                    print(f'Test {test}: OK in {queries_used} queries.')
                    max_queries_used = max( max_queries_used, queries_used )
                else:
                    error(f'Test {test}: Wrong answer: returned permutation is not the correct permutation.')

                break # terminate this test, start the next one

if __name__ == "__main__":
    try:
        main()
    except KeyboardInterrupt:
        pass
