#include <bits/stdc++.h>
using namespace std;
template <class T>
using min_queue = priority_queue<T, vector<T>, greater<T>>;
const int INF = static_cast<int>(1e9);
const long long INF_LL = static_cast<long long>(4e18);
const double pi = acos(-1.0);
template <class T>
inline T& smin(T& x, const T& y) {
  return x > y ? x = y : x;
}
template <class T>
inline T& smax(T& x, const T& y) {
  return x < y ? x = y : x;
}
template <class T>
inline T sqr(const T& x) {
  return x * x;
}
template <class T>
inline int sgn(const T& x) {
  return (T(0) < x) - (x < T(0));
}
template <class T>
T gcd(T a, T b) {
  for (a = abs(a), b = abs(b); a && b; a >= b ? a %= b : b %= a)
    ;
  return a + b;
}
template <class T>
struct is_commutative {
  constexpr static bool value = true;
};
using uint = unsigned int;
const uint BUFFER_SIZE = 1 << 12;
const uint MAX_LENGTH = 1 << 7;
namespace Detail {
struct Width {
  uint value;
};
struct Fill {
  char value;
};
struct Base {
  uint value;
};
struct Precision {
  uint value;
};
struct Delimiter {
  const char* value;
};
}  // namespace Detail
Detail::Width setWidth(uint value = 0) { return {value}; }
Detail::Fill setFill(char value = ' ') { return {value}; }
Detail::Base setBase(uint value = 10) {
  assert(2 <= value && value <= 36);
  return {value};
}
Detail::Precision setPrecision(uint value = 9) {
  assert(value < MAX_LENGTH);
  return {value};
}
Detail::Delimiter setDelimiter(const char* value = " ") { return {value}; }
class InputDevice {
 protected:
  const char* head;
  const char* tail;
  InputDevice(const char* head, const char* tail)
      : head(head), tail(tail), base(setBase().value) {}
  virtual void fillInput() = 0;
  inline char nextChar() {
    if (__builtin_expect(head >= tail, false)) fillInput();
    return *head++;
  }
  template <class I>
  int readUnsignedIntGeneral(I& arg, char c) {
    I value = 0;
    int length = 0;
    for (;; ++length, c = nextChar()) {
      if (isDigit(c))
        c -= '0';
      else if (isUpper(c))
        c -= 'A' - 10;
      else if (isLower(c))
        c -= 'a' - 10;
      else
        c = base;
      if (c >= base) break;
      value = base * value + c;
    }
    arg = value;
    return --head, length;
  }
  template <class I>
  inline int readUnsignedInt(I& arg, char c) {
    if (__builtin_expect(base > 10, false))
      return readUnsignedIntGeneral(arg, c);
    I value = 0;
    int length = 0;
    for (; static_cast<unsigned char>(c - '0') < base; ++length, c = nextChar())
      value = base * value + c - '0';
    arg = value;
    return --head, length;
  }
  template <class I>
  inline bool readSignedInt(I& arg, char c) {
    bool negative = c == '-';
    if (negative) c = nextChar();
    typename make_unsigned<I>::type unsignedArg;
    if (readUnsignedInt(unsignedArg, c) == 0) return false;
    arg = negative ? ~static_cast<I>(unsignedArg - 1)
                   : static_cast<I>(unsignedArg);
    return true;
  }
  template <class F>
  bool readFloatingPoint(F& arg, char c) {
    bool negative = c == '-';
    if (negative) c = nextChar();
    unsigned long long integerPart;
    if (readUnsignedInt(integerPart, c) == 0) return false;
    arg = static_cast<F>(integerPart);
    if (nextChar() == '.') {
      unsigned long long fractionalPart = 0;
      int fractionalLength = readUnsignedInt(fractionalPart, nextChar());
      if (fractionalLength > 0) {
        unsigned long long basePower = 1;
        for (; fractionalLength; --fractionalLength) basePower *= base;
        arg += static_cast<F>(fractionalPart) / basePower;
      }
    } else
      --head;
    if (negative) arg = -arg;
    return true;
  }

 public:
  uint base;
  InputDevice(InputDevice const&) = delete;
  InputDevice& operator=(InputDevice const&) = delete;
  static inline bool isSpace(char c) {
    return static_cast<unsigned char>(c - '\t') < 5 || c == ' ';
  }
  static inline bool isDigit(char c) {
    return static_cast<unsigned char>(c - '0') < 10;
  }
  static inline bool isUpper(char c) {
    return static_cast<unsigned char>(c - 'A') < 26;
  }
  static inline bool isLower(char c) {
    return static_cast<unsigned char>(c - 'a') < 26;
  }
  static inline bool isOneOf(char c, const char* str) {
    return strchr(str, c) != nullptr;
  }
  void putBack() { --head; }
  inline bool readChar(char& arg) {
    if (__builtin_expect(head >= tail, false)) {
      fillInput();
      if (__builtin_expect(head >= tail, false)) return arg = '\0', false;
    }
    return arg = *head++, true;
  }
  template <class UnaryPredicate>
  inline char skipCharacters(UnaryPredicate isSkipped) {
    char c;
    do {
      c = nextChar();
    } while (isSkipped(c));
    return c;
  }
  inline char skipCharacters() { return skipCharacters(isSpace); }
  template <class UnaryPredicate>
  inline bool readString(char* arg, int limit, UnaryPredicate isTerminator) {
    skipCharacters(isTerminator);
    for (--head, --limit; head < tail; fillInput()) {
      ptrdiff_t chunkSize =
          find_if(head, min(tail, head + limit), isTerminator) - head;
      arg = copy_n(head, chunkSize, arg);
      head += chunkSize;
      limit -= chunkSize;
      if (chunkSize == 0 || head < tail) break;
    }
    return *arg = '\0', true;
  }
  template <class I>
  inline bool readUnsignedInt(I& arg) {
    return readUnsignedInt(arg, skipCharacters()) > 0;
  }
  template <class I>
  inline bool readSignedInt(I& arg) {
    return readSignedInt(arg, skipCharacters());
  }
  template <class F>
  inline bool readFloatingPoint(F& arg) {
    return readFloatingPoint(arg, skipCharacters());
  }
};
class InputFile : public InputDevice {
  FILE* file;
  bool lineBuffered;
  bool owner;
  char buffer[BUFFER_SIZE];
  void fillInput() override {
    head = buffer;
    *buffer = '\0';
    if (__builtin_expect(!lineBuffered, true)) {
      tail = head + fread(buffer, 1, BUFFER_SIZE, file);
    } else {
      tail = head;
      if (fgets(buffer, BUFFER_SIZE, file))
        while (*tail) ++tail;
    }
  }

 public:
  InputFile(FILE* file = stdin, bool lineBuffered = true,
            bool takeOwnership = false)
      : InputDevice(buffer, buffer),
        file(file),
        lineBuffered(lineBuffered),
        owner(takeOwnership) {}
  InputFile(const char* fileName)
      : InputFile(fopen(fileName, "r"), false, true) {}
  ~InputFile() {
    if (owner) fclose(file);
  }
};
class InputString : public InputDevice {
  void fillInput() override {
    while (*tail) ++tail;
  }

 public:
  InputString(const string& s) : InputDevice(s.data(), s.data() + s.size()) {}
  InputString(const char* s) : InputDevice(s, s + strlen(s)) {}
};
class OutputDevice {
 protected:
  char buffer[BUFFER_SIZE + MAX_LENGTH];
  char* output;
  char* end;
  bool separate;
  OutputDevice()
      : output(buffer),
        end(buffer + BUFFER_SIZE + MAX_LENGTH),
        separate(false),
        width(setWidth().value),
        fill(setFill().value),
        base(setBase().value),
        precision(setPrecision().value),
        delimiter(setDelimiter().value) {
    computeBasePower();
  }
  virtual void writeToDevice(uint count) = 0;
  inline void flushMaybe() {
    if (__builtin_expect(output >= buffer + BUFFER_SIZE, false)) {
      writeToDevice(BUFFER_SIZE);
      output = copy(buffer + BUFFER_SIZE, output, buffer);
    }
  }
  template <class I>
  inline char* writeUnsignedInt(I arg, char* last) {
    if (__builtin_expect(arg == 0, false)) *--last = '0';
    if (__builtin_expect(base == 10, true)) {
      for (; arg; arg /= 10) *--last = '0' + arg % 10;
    } else
      for (; arg; arg /= base) {
        I digit = arg % base;
        *--last = digit < 10 ? '0' + digit : 'A' - 10 + digit;
      }
    return last;
  }
  template <class I>
  inline char* writeSignedInt(I arg, char* last) {
    auto unsignedArg = static_cast<typename make_unsigned<I>::type>(arg);
    if (arg < 0) {
      last = writeUnsignedInt(~unsignedArg + 1, last);
      *--last = '-';
      return last;
    }
    return writeUnsignedInt(unsignedArg, last);
  }
  template <class F>
  char* writeFloatingPoint(F arg, char* last) {
    bool negative = signbit(arg);
    if (negative) arg = -arg;
    if (isnan(arg))
      for (int i = 0; i < 3; ++i) *--last = i["NaN"];
    else if (isinf(arg))
      for (int i = 0; i < 3; ++i) *--last = i["fnI"];
    else {
      auto integerPart = static_cast<unsigned long long>(arg);
      auto fractionalPart = static_cast<unsigned long long>(
          (arg - integerPart) * basePower + F(0.5));
      if (fractionalPart >= basePower) ++integerPart, fractionalPart = 0;
      char* point = last - precision;
      if (precision > 0) {
        ::fill(point, writeUnsignedInt(fractionalPart, last), '0');
        *--point = '.';
      }
      last = writeUnsignedInt(integerPart, point);
    }
    if (negative) *--last = '-';
    return last;
  }
  inline int writeT(char* first) {
    int delimiterLenght = separate ? writeDelimiter() : 0;
    separate = true;
    int charsWritten = static_cast<int>(end - first);
    if (__builtin_expect(charsWritten < width, false))
      charsWritten += writeFill(width - charsWritten);
    output = copy(first, end, output);
    flushMaybe();
    return delimiterLenght + charsWritten;
  }
  inline int writeFill(int count) {
    int result = count;
    if (__builtin_expect(output + count + MAX_LENGTH < end, true)) {
      if (count == 1)
        *output++ = fill;
      else
        output = fill_n(output, count, fill);
    } else
      for (uint chunkSize = static_cast<uint>(buffer + BUFFER_SIZE - output);;
           chunkSize = BUFFER_SIZE) {
        if (chunkSize > count) chunkSize = count;
        output = fill_n(output, chunkSize, fill);
        flushMaybe();
        if ((count -= chunkSize) == 0) break;
      }
    return result;
  }

 public:
  int width;
  char fill;
  uint base;
  uint precision;
  unsigned long long basePower;
  string delimiter;
  OutputDevice(OutputDevice const&) = delete;
  OutputDevice& operator=(OutputDevice const&) = delete;
  virtual ~OutputDevice(){};
  void computeBasePower() {
    basePower = 1;
    for (uint i = 0; i < precision; ++i) basePower *= base;
  }
  inline int writeChar(char arg) {
    separate = false;
    *output++ = arg;
    flushMaybe();
    return 1;
  }
  inline int writeString(const char* arg, int count, bool checkWidth = true) {
    separate = false;
    int result =
        count + (checkWidth && count < width ? writeFill(width - count) : 0);
    if (__builtin_expect(output + count + MAX_LENGTH < end, true)) {
      if (count == 1)
        *output++ = *arg;
      else
        output = copy_n(arg, count, output);
    } else
      for (int chunkSize = static_cast<int>(buffer + BUFFER_SIZE - output);;
           chunkSize = BUFFER_SIZE) {
        if (chunkSize > count) chunkSize = count;
        output = copy_n(arg, chunkSize, output);
        flushMaybe();
        if ((count -= chunkSize) == 0) break;
        arg += chunkSize;
      }
    return result;
  }
  inline int writeDelimiter() {
    return writeString(delimiter.c_str(), static_cast<int>(delimiter.size()),
                       false);
  }
  template <class I>
  inline int writeUnsignedInt(I arg) {
    return writeT(writeUnsignedInt(arg, end));
  }
  template <class I>
  inline int writeSignedInt(I arg) {
    return writeT(writeSignedInt(arg, end));
  }
  template <class F>
  inline int writeFloatingPoint(F arg) {
    return writeT(writeFloatingPoint(arg, end));
  }
  inline void flush() {
    writeToDevice(static_cast<uint>(output - buffer));
    output = buffer;
  }
};
class OutputFile : public OutputDevice {
  FILE* file;
  bool owner;
  void writeToDevice(uint count) override {
    fwrite(buffer, 1, count, file);
    fflush(file);
  }

 public:
  OutputFile(FILE* file = stdout, bool takeOwnership = false)
      : file(file), owner(takeOwnership) {}
  OutputFile(const char* fileName) : OutputFile(fopen(fileName, "w"), true) {}
  ~OutputFile() override {
    flush();
    if (owner) fclose(file);
  }
};
class OutputString : public OutputDevice {
  string& str;
  void writeToDevice(uint count) override { str.append(buffer, count); }

 public:
  OutputString(string& str) : OutputDevice(), str(str) {}
  ~OutputString() override { flush(); }
};
unique_ptr<InputFile> input;
unique_ptr<OutputFile> output;
inline int read(Detail::Base base) {
  input->base = base.value;
  return 0;
}
inline int read() { return 0; }
inline int read(char& arg) { return input->readChar(arg); }
template <class I>
inline typename enable_if<is_integral<I>::value && is_unsigned<I>::value,
                          int>::type
read(I& arg) {
  return input->readUnsignedInt(arg);
}
template <class I>
inline
    typename enable_if<is_integral<I>::value && is_signed<I>::value, int>::type
    read(I& arg) {
  return input->readSignedInt(arg);
}
template <class F>
inline typename enable_if<is_floating_point<F>::value, int>::type read(F& arg) {
  return input->readFloatingPoint(arg);
}
inline int read(const char& arg) {
  input->skipCharacters([arg](char c) { return arg != c; });
  return 0;
}
inline int read(const char* arg) {
  if (*arg)
    input->skipCharacters(
        [arg](char c) { return InputDevice::isOneOf(c, arg); });
  else
    input->skipCharacters();
  input->putBack();
  return 0;
}
inline int read(bool (*isSkipped)(char)) {
  input->skipCharacters(isSkipped);
  input->putBack();
  return 0;
}
template <class... Ts>
int read(char* arg, int limit, bool (*isTerminator)(char), Ts&&... args);
template <class... Ts>
int read(char* arg, int limit, const char* terminators, Ts&&... args);
template <class Iterator, class... Ts,
          typename = decltype(*std::declval<Iterator>())>
int read(Iterator first, Iterator last, Ts&&... args);
template <class Iterator, class... Ts,
          typename = decltype(*std::declval<Iterator>())>
int read(Iterator first, int count, Ts&&... args);
template <class T0, class T1, class... Ts,
          typename =
              typename enable_if<!is_convertible<T0, char*>::value, void>::type>
int read(T0&& arg0, T1&& arg1, Ts&&... args);
inline int read(char* arg, int limit, const char* terminators = "") {
  if (!*terminators)
    return input->readString(arg, limit, InputDevice::isSpace);
  else
    return input->readString(arg, limit, [terminators](char c) {
      return InputDevice::isOneOf(c, terminators);
    });
}
template <class... Ts>
inline int read(char* first, char* last, Ts&&... args) {
  return read(first, static_cast<int>(last - first), forward<Ts>(args)...);
}
template <int N, class... Ts>
inline int read(char (&arg)[N], Ts&&... args) {
  return read(static_cast<char*>(arg), N, forward<Ts>(args)...);
}
template <class... Ts>
inline int read(char* arg, int limit, bool (*isTerminator)(char),
                Ts&&... args) {
  int argsRead = input->readString(arg, limit, isTerminator);
  return argsRead + read(forward<Ts>(args)...);
}
template <class... Ts>
inline int read(char* arg, int limit, const char* terminators, Ts&&... args) {
  int argsRead = read(arg, limit, terminators);
  return argsRead + read(forward<Ts>(args)...);
}
template <class T1, class T2>
inline int read(pair<T1, T2>& arg) {
  return read(arg.first) == 1 && read(arg.second) == 1 ? 1 : 0;
}
template <class T>
inline int read(vector<T>& arg) {
  uint n;
  if (read(n) == 0) return 0;
  arg.resize(n);
  return read(arg.begin(), arg.end());
}
template <class Iterator, class... Ts, typename>
int read(Iterator first, Iterator last, Ts&&... args) {
  int success = 1;
  for (; first != last; ++first) success &= read(*first);
  return success + read(forward<Ts>(args)...);
}
template <class Iterator, class... Ts, typename>
int read(Iterator first, int count, Ts&&... args) {
  return read(first, first + count, forward<Ts>(args)...);
}
template <class T0, class T1, class... Ts, typename>
inline int read(T0&& arg0, T1&& arg1, Ts&&... args) {
  int argsRead = read(forward<T0>(arg0));
  return argsRead + read(forward<T1>(arg1), forward<Ts>(args)...);
}
inline int write(Detail::Width width) {
  output->width = static_cast<int>(width.value);
  return 0;
}
inline int write(Detail::Fill fill) {
  output->fill = fill.value;
  return 0;
}
inline int write(Detail::Base base) {
  output->base = base.value;
  output->computeBasePower();
  return 0;
}
inline int write(Detail::Precision precision) {
  output->precision = precision.value;
  output->computeBasePower();
  return 0;
}
inline int write(Detail::Delimiter delimiter) {
  output->delimiter = delimiter.value;
  return 0;
}
inline int write() { return 0; }
inline int write(char arg) { return output->writeChar(arg); }
template <class I>
inline typename enable_if<is_integral<I>::value && is_unsigned<I>::value,
                          int>::type
write(I arg) {
  return output->writeUnsignedInt(arg);
}
template <class I>
inline
    typename enable_if<is_integral<I>::value && is_signed<I>::value, int>::type
    write(I arg) {
  return output->writeSignedInt(arg);
}
template <class F>
inline typename enable_if<is_floating_point<F>::value, int>::type write(F arg) {
  return output->writeFloatingPoint(arg);
}
inline int write(const char* arg) {
  return output->writeString(arg, static_cast<int>(strlen(arg)));
}
template <int N>
inline int write(char (&arg)[N]) {
  return output->writeString(arg, static_cast<int>(strlen(arg)));
}
inline int write(const string& arg) {
  return output->writeString(arg.c_str(), static_cast<int>(arg.size()));
}
template <class T1, class T2>
inline int write(const pair<T1, T2>& arg) {
  int charsWritten = write(arg.first);
  charsWritten += output->writeDelimiter();
  return charsWritten + write(arg.second);
}
template <
    class Iterator, class... Ts,
    typename = typename enable_if<!is_convertible<Iterator, const char*>::value,
                                  decltype(*std::declval<Iterator>())>::type>
int write(Iterator first, Iterator last, Ts&&... args);
template <
    class Iterator, class... Ts,
    typename = typename enable_if<!is_convertible<Iterator, const char*>::value,
                                  decltype(*std::declval<Iterator>())>::type>
int write(Iterator first, int count, Ts&&... args);
template <class T, class T2, class... Ts>
int write(T&& arg, T2&& arg2, Ts&&... args);
template <class Iterator, class... Ts, typename>
int write(Iterator first, Iterator last, Ts&&... args) {
  int charsWritten = 0;
  for (; first != last;
       charsWritten += ++first == last ? 0 : output->writeDelimiter())
    charsWritten += write(*first);
  return charsWritten + write(forward<Ts>(args)...);
}
template <class Iterator, class... Ts, typename>
int write(Iterator first, int count, Ts&&... args) {
  return write(first, first + count, forward<Ts>(args)...);
}
template <class T, class T2, class... Ts>
inline int write(T&& arg, T2&& arg2, Ts&&... args) {
  int charsWritten = write(forward<T>(arg));
  return charsWritten + write(forward<T2>(arg2), forward<Ts>(args)...);
}
template <class... Ts>
inline int writeln(Ts&&... args) {
  return write(forward<Ts>(args)..., '\n');
}
void flush() { output->flush(); }
vector<vector<int>> e;
vector<int> p;
int h;
int query(int v) {
  int k;
  writeln("? ", v);
  flush();
  read(k);
  if (k == 0) exit(0);
  p.push_back(v);
  e[v].resize(k);
  read((e[v]).begin(), (e[v]).end());
  if (k == 2) {
    writeln("! ", v);
    flush();
  }
  return k;
}
bool find1(int v, int forb, bool first = false) {
  int k = query(v);
  if (k == 1) return false;
  if (k == 2) return true;
  if (!first && (h >= 6 && static_cast<int>((p).size()) == 2 * h - 5)) {
    p.push_back(-1);
    p.push_back(-1);
    return false;
  }
  for (int u : e[v])
    if (u != forb) return find1(u, v, first);
  return false;
}
void solve() {
  e.assign(1 << h, vector<int>());
  p.clear();
  if (find1(1, -1, true)) return;
  reverse((p).begin(), (p).end());
  int v = p.back();
  if (static_cast<int>((e[v]).size()) != 1) {
    for (int u : e[v])
      if (u != p[static_cast<int>((p).size()) - 2]) {
        if (find1(u, v)) return;
        break;
      }
  }
  while (true) {
    int m = static_cast<int>((p).size()) / 2;
    v = p[m];
    vector<int> forb;
    if (m != 0) forb = {p[m - 1], p[m + 1]};
    p.erase(p.begin() + m + 1, p.end());
    if (static_cast<int>((p).size()) == h - 3) {
      for (int u : e[v])
        if (find((forb).begin(), (forb).end(), u) == forb.end()) {
          int k = query(u);
          if (k == 2) return;
          vector<int> c;
          for (int x : e[u])
            if (x != v) {
              k = query(x);
              if (k == 2) return;
              for (int y : e[x])
                if (y != u) c.push_back(y);
            }
          for (int i(0), b_(static_cast<int>((c).size()) - 1); i < b_; ++i)
            if (query(c[i]) == 2) return;
          writeln("! ", c.back());
          flush();
          return;
        }
    }
    for (int u : e[v])
      if (find((forb).begin(), (forb).end(), u) == forb.end()) {
        if (static_cast<int>((p).size()) == h - 1) {
          writeln("! ", u);
          flush();
          return;
        } else if (static_cast<int>((p).size()) == h - 2) {
          int k = query(u);
          if (k == 3) {
            vector<int> c;
            for (int x : e[u])
              if (x != v) c.push_back(x);
            if (query(c[0]) != 2) {
              writeln("! ", c[1]);
              flush();
            }
          }
          return;
        } else if (find1(u, v))
          return;
      }
  }
}
int main() {
  input.reset(new InputFile());
  output.reset(new OutputFile());
  int t;
  read(t);
  for (int it(0), b_(t); it < b_; ++it) {
    read(h);
    if (h == 0) return 0;
    solve();
  }
  return 0;
}

### Prompt

Your task is to create a Cpp solution to the following problem:

This is an interactive problem. In the interaction section below you will find the information about flushing the output.

The New Year tree of height h is a perfect binary tree with vertices numbered 1 through 2h - 1 in some order. In this problem we assume that h is at least 2. The drawing below shows one example New Year tree of height 3:

<image>

Polar bears love decorating the New Year tree and Limak is no exception. To decorate the tree, he must first find its root, i.e. a vertex with exactly two neighbours (assuming that h ≥ 2). It won't be easy because Limak is a little bear and he doesn't even see the whole tree. Can you help him?

There are t testcases. In each testcase, you should first read h from the input. Then you can ask at most 16 questions of format "? x" (without quotes), where x is an integer between 1 and 2h - 1, inclusive. As a reply you will get the list of neighbours of vertex x (more details in the "Interaction" section below). For example, for a tree on the drawing above after asking "? 1" you would get a response with 3 neighbours: 4, 5 and 7. Your goal is to find the index of the root y and print it in the format "! y". You will be able to read h for a next testcase only after printing the answer in a previous testcase and flushing the output.

Each tree is fixed from the beginning and it doesn't change during your questions.

Input

The first line of the input contains a single integer t (1 ≤ t ≤ 500) — the number of testcases.

At the beginning of each testcase you should read from the input a single integer h (2 ≤ h ≤ 7) — the height of the tree. You can't read the value of h in a next testcase until you answer a previous testcase.

Interaction

To ask a question about neighbours of vertex x, print "? x" (without quotes) on a separate line. Note, you must print an end-of-line character after the last character of the line and flush your output to get a response.

The response will consist of two lines. The first line will contain a single integer k (1 ≤ k ≤ 3) — the number of neighbours of vertex x. The second line will contain k distinct integers t1, ..., tk (1 ≤ t1 < ... < tk ≤ 2h - 1) — indices of neighbours of vertex x, gives in the increasing order.

After asking at most 16 questions you have to say y — the index of the root. Print "! y" (without quotes) and an end-of-line character, and flush the output.

Each tree is fixed from the beginning and it doesn't change during your questions.

You can get Idleness Limit Exceeded if you don't print anything or if you forget to flush the output.

To flush you can use (just printing a query/answer and end-of-line): 

  * fflush(stdout) in C++; 
  * System.out.flush() in Java; 
  * stdout.flush() in Python; 
  * flush(output) in Pascal; 
  * See the documentation for other languages. 



In any moment if the program reads h = 0 or k = 0 it should immediately terminate normally (for example, calling exit(0)). It means that the system detected incorrect request/output from your program and printed 0 because if can't process your requests anymore. In this case you'll receive verdict "Wrong Answer", but if you ignore case h = 0 or k = 0 it could lead to "Runtime Error", "Time/Memory limit exceeded" or any other verdict because your program could read a trash from the closed input stream.

Hacking. To hack someone, use the following format:

The first line should contain a single integer t equal to 1 (only one testcase is allowed in hacks). The second line should contain a single integer h. Each of next 2h - 2 lines should contain two distinct integers ai and bi (1 ≤ ai, bi ≤ 2h - 1), denoting two nodes connected with an edge. The printed edges must form a perfect binary tree of height h.

Of course, contestant programs will not be able to see this input.

Examples

Input

1
3
3
4 5 7
2
1 2
1
2


Output

? 1
? 5
? 6
! 5


Input

2
2
1
3
2
1 2
2
1 2
4
3
3 12 13


Output

? 1
? 3
? 3
! 3
? 6
! 1

Note

In the first sample, a tree corresponds to the drawing from the statement.

In the second sample, there are two two testcases. A tree in the first testcase has height 2 and thus 3 vertices. A tree in the second testcase has height 4 and thus 15 vertices. You can see both trees on the drawing below.

<image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class T>
using min_queue = priority_queue<T, vector<T>, greater<T>>;
const int INF = static_cast<int>(1e9);
const long long INF_LL = static_cast<long long>(4e18);
const double pi = acos(-1.0);
template <class T>
inline T& smin(T& x, const T& y) {
  return x > y ? x = y : x;
}
template <class T>
inline T& smax(T& x, const T& y) {
  return x < y ? x = y : x;
}
template <class T>
inline T sqr(const T& x) {
  return x * x;
}
template <class T>
inline int sgn(const T& x) {
  return (T(0) < x) - (x < T(0));
}
template <class T>
T gcd(T a, T b) {
  for (a = abs(a), b = abs(b); a && b; a >= b ? a %= b : b %= a)
    ;
  return a + b;
}
template <class T>
struct is_commutative {
  constexpr static bool value = true;
};
using uint = unsigned int;
const uint BUFFER_SIZE = 1 << 12;
const uint MAX_LENGTH = 1 << 7;
namespace Detail {
struct Width {
  uint value;
};
struct Fill {
  char value;
};
struct Base {
  uint value;
};
struct Precision {
  uint value;
};
struct Delimiter {
  const char* value;
};
}  // namespace Detail
Detail::Width setWidth(uint value = 0) { return {value}; }
Detail::Fill setFill(char value = ' ') { return {value}; }
Detail::Base setBase(uint value = 10) {
  assert(2 <= value && value <= 36);
  return {value};
}
Detail::Precision setPrecision(uint value = 9) {
  assert(value < MAX_LENGTH);
  return {value};
}
Detail::Delimiter setDelimiter(const char* value = " ") { return {value}; }
class InputDevice {
 protected:
  const char* head;
  const char* tail;
  InputDevice(const char* head, const char* tail)
      : head(head), tail(tail), base(setBase().value) {}
  virtual void fillInput() = 0;
  inline char nextChar() {
    if (__builtin_expect(head >= tail, false)) fillInput();
    return *head++;
  }
  template <class I>
  int readUnsignedIntGeneral(I& arg, char c) {
    I value = 0;
    int length = 0;
    for (;; ++length, c = nextChar()) {
      if (isDigit(c))
        c -= '0';
      else if (isUpper(c))
        c -= 'A' - 10;
      else if (isLower(c))
        c -= 'a' - 10;
      else
        c = base;
      if (c >= base) break;
      value = base * value + c;
    }
    arg = value;
    return --head, length;
  }
  template <class I>
  inline int readUnsignedInt(I& arg, char c) {
    if (__builtin_expect(base > 10, false))
      return readUnsignedIntGeneral(arg, c);
    I value = 0;
    int length = 0;
    for (; static_cast<unsigned char>(c - '0') < base; ++length, c = nextChar())
      value = base * value + c - '0';
    arg = value;
    return --head, length;
  }
  template <class I>
  inline bool readSignedInt(I& arg, char c) {
    bool negative = c == '-';
    if (negative) c = nextChar();
    typename make_unsigned<I>::type unsignedArg;
    if (readUnsignedInt(unsignedArg, c) == 0) return false;
    arg = negative ? ~static_cast<I>(unsignedArg - 1)
                   : static_cast<I>(unsignedArg);
    return true;
  }
  template <class F>
  bool readFloatingPoint(F& arg, char c) {
    bool negative = c == '-';
    if (negative) c = nextChar();
    unsigned long long integerPart;
    if (readUnsignedInt(integerPart, c) == 0) return false;
    arg = static_cast<F>(integerPart);
    if (nextChar() == '.') {
      unsigned long long fractionalPart = 0;
      int fractionalLength = readUnsignedInt(fractionalPart, nextChar());
      if (fractionalLength > 0) {
        unsigned long long basePower = 1;
        for (; fractionalLength; --fractionalLength) basePower *= base;
        arg += static_cast<F>(fractionalPart) / basePower;
      }
    } else
      --head;
    if (negative) arg = -arg;
    return true;
  }

 public:
  uint base;
  InputDevice(InputDevice const&) = delete;
  InputDevice& operator=(InputDevice const&) = delete;
  static inline bool isSpace(char c) {
    return static_cast<unsigned char>(c - '\t') < 5 || c == ' ';
  }
  static inline bool isDigit(char c) {
    return static_cast<unsigned char>(c - '0') < 10;
  }
  static inline bool isUpper(char c) {
    return static_cast<unsigned char>(c - 'A') < 26;
  }
  static inline bool isLower(char c) {
    return static_cast<unsigned char>(c - 'a') < 26;
  }
  static inline bool isOneOf(char c, const char* str) {
    return strchr(str, c) != nullptr;
  }
  void putBack() { --head; }
  inline bool readChar(char& arg) {
    if (__builtin_expect(head >= tail, false)) {
      fillInput();
      if (__builtin_expect(head >= tail, false)) return arg = '\0', false;
    }
    return arg = *head++, true;
  }
  template <class UnaryPredicate>
  inline char skipCharacters(UnaryPredicate isSkipped) {
    char c;
    do {
      c = nextChar();
    } while (isSkipped(c));
    return c;
  }
  inline char skipCharacters() { return skipCharacters(isSpace); }
  template <class UnaryPredicate>
  inline bool readString(char* arg, int limit, UnaryPredicate isTerminator) {
    skipCharacters(isTerminator);
    for (--head, --limit; head < tail; fillInput()) {
      ptrdiff_t chunkSize =
          find_if(head, min(tail, head + limit), isTerminator) - head;
      arg = copy_n(head, chunkSize, arg);
      head += chunkSize;
      limit -= chunkSize;
      if (chunkSize == 0 || head < tail) break;
    }
    return *arg = '\0', true;
  }
  template <class I>
  inline bool readUnsignedInt(I& arg) {
    return readUnsignedInt(arg, skipCharacters()) > 0;
  }
  template <class I>
  inline bool readSignedInt(I& arg) {
    return readSignedInt(arg, skipCharacters());
  }
  template <class F>
  inline bool readFloatingPoint(F& arg) {
    return readFloatingPoint(arg, skipCharacters());
  }
};
class InputFile : public InputDevice {
  FILE* file;
  bool lineBuffered;
  bool owner;
  char buffer[BUFFER_SIZE];
  void fillInput() override {
    head = buffer;
    *buffer = '\0';
    if (__builtin_expect(!lineBuffered, true)) {
      tail = head + fread(buffer, 1, BUFFER_SIZE, file);
    } else {
      tail = head;
      if (fgets(buffer, BUFFER_SIZE, file))
        while (*tail) ++tail;
    }
  }

 public:
  InputFile(FILE* file = stdin, bool lineBuffered = true,
            bool takeOwnership = false)
      : InputDevice(buffer, buffer),
        file(file),
        lineBuffered(lineBuffered),
        owner(takeOwnership) {}
  InputFile(const char* fileName)
      : InputFile(fopen(fileName, "r"), false, true) {}
  ~InputFile() {
    if (owner) fclose(file);
  }
};
class InputString : public InputDevice {
  void fillInput() override {
    while (*tail) ++tail;
  }

 public:
  InputString(const string& s) : InputDevice(s.data(), s.data() + s.size()) {}
  InputString(const char* s) : InputDevice(s, s + strlen(s)) {}
};
class OutputDevice {
 protected:
  char buffer[BUFFER_SIZE + MAX_LENGTH];
  char* output;
  char* end;
  bool separate;
  OutputDevice()
      : output(buffer),
        end(buffer + BUFFER_SIZE + MAX_LENGTH),
        separate(false),
        width(setWidth().value),
        fill(setFill().value),
        base(setBase().value),
        precision(setPrecision().value),
        delimiter(setDelimiter().value) {
    computeBasePower();
  }
  virtual void writeToDevice(uint count) = 0;
  inline void flushMaybe() {
    if (__builtin_expect(output >= buffer + BUFFER_SIZE, false)) {
      writeToDevice(BUFFER_SIZE);
      output = copy(buffer + BUFFER_SIZE, output, buffer);
    }
  }
  template <class I>
  inline char* writeUnsignedInt(I arg, char* last) {
    if (__builtin_expect(arg == 0, false)) *--last = '0';
    if (__builtin_expect(base == 10, true)) {
      for (; arg; arg /= 10) *--last = '0' + arg % 10;
    } else
      for (; arg; arg /= base) {
        I digit = arg % base;
        *--last = digit < 10 ? '0' + digit : 'A' - 10 + digit;
      }
    return last;
  }
  template <class I>
  inline char* writeSignedInt(I arg, char* last) {
    auto unsignedArg = static_cast<typename make_unsigned<I>::type>(arg);
    if (arg < 0) {
      last = writeUnsignedInt(~unsignedArg + 1, last);
      *--last = '-';
      return last;
    }
    return writeUnsignedInt(unsignedArg, last);
  }
  template <class F>
  char* writeFloatingPoint(F arg, char* last) {
    bool negative = signbit(arg);
    if (negative) arg = -arg;
    if (isnan(arg))
      for (int i = 0; i < 3; ++i) *--last = i["NaN"];
    else if (isinf(arg))
      for (int i = 0; i < 3; ++i) *--last = i["fnI"];
    else {
      auto integerPart = static_cast<unsigned long long>(arg);
      auto fractionalPart = static_cast<unsigned long long>(
          (arg - integerPart) * basePower + F(0.5));
      if (fractionalPart >= basePower) ++integerPart, fractionalPart = 0;
      char* point = last - precision;
      if (precision > 0) {
        ::fill(point, writeUnsignedInt(fractionalPart, last), '0');
        *--point = '.';
      }
      last = writeUnsignedInt(integerPart, point);
    }
    if (negative) *--last = '-';
    return last;
  }
  inline int writeT(char* first) {
    int delimiterLenght = separate ? writeDelimiter() : 0;
    separate = true;
    int charsWritten = static_cast<int>(end - first);
    if (__builtin_expect(charsWritten < width, false))
      charsWritten += writeFill(width - charsWritten);
    output = copy(first, end, output);
    flushMaybe();
    return delimiterLenght + charsWritten;
  }
  inline int writeFill(int count) {
    int result = count;
    if (__builtin_expect(output + count + MAX_LENGTH < end, true)) {
      if (count == 1)
        *output++ = fill;
      else
        output = fill_n(output, count, fill);
    } else
      for (uint chunkSize = static_cast<uint>(buffer + BUFFER_SIZE - output);;
           chunkSize = BUFFER_SIZE) {
        if (chunkSize > count) chunkSize = count;
        output = fill_n(output, chunkSize, fill);
        flushMaybe();
        if ((count -= chunkSize) == 0) break;
      }
    return result;
  }

 public:
  int width;
  char fill;
  uint base;
  uint precision;
  unsigned long long basePower;
  string delimiter;
  OutputDevice(OutputDevice const&) = delete;
  OutputDevice& operator=(OutputDevice const&) = delete;
  virtual ~OutputDevice(){};
  void computeBasePower() {
    basePower = 1;
    for (uint i = 0; i < precision; ++i) basePower *= base;
  }
  inline int writeChar(char arg) {
    separate = false;
    *output++ = arg;
    flushMaybe();
    return 1;
  }
  inline int writeString(const char* arg, int count, bool checkWidth = true) {
    separate = false;
    int result =
        count + (checkWidth && count < width ? writeFill(width - count) : 0);
    if (__builtin_expect(output + count + MAX_LENGTH < end, true)) {
      if (count == 1)
        *output++ = *arg;
      else
        output = copy_n(arg, count, output);
    } else
      for (int chunkSize = static_cast<int>(buffer + BUFFER_SIZE - output);;
           chunkSize = BUFFER_SIZE) {
        if (chunkSize > count) chunkSize = count;
        output = copy_n(arg, chunkSize, output);
        flushMaybe();
        if ((count -= chunkSize) == 0) break;
        arg += chunkSize;
      }
    return result;
  }
  inline int writeDelimiter() {
    return writeString(delimiter.c_str(), static_cast<int>(delimiter.size()),
                       false);
  }
  template <class I>
  inline int writeUnsignedInt(I arg) {
    return writeT(writeUnsignedInt(arg, end));
  }
  template <class I>
  inline int writeSignedInt(I arg) {
    return writeT(writeSignedInt(arg, end));
  }
  template <class F>
  inline int writeFloatingPoint(F arg) {
    return writeT(writeFloatingPoint(arg, end));
  }
  inline void flush() {
    writeToDevice(static_cast<uint>(output - buffer));
    output = buffer;
  }
};
class OutputFile : public OutputDevice {
  FILE* file;
  bool owner;
  void writeToDevice(uint count) override {
    fwrite(buffer, 1, count, file);
    fflush(file);
  }

 public:
  OutputFile(FILE* file = stdout, bool takeOwnership = false)
      : file(file), owner(takeOwnership) {}
  OutputFile(const char* fileName) : OutputFile(fopen(fileName, "w"), true) {}
  ~OutputFile() override {
    flush();
    if (owner) fclose(file);
  }
};
class OutputString : public OutputDevice {
  string& str;
  void writeToDevice(uint count) override { str.append(buffer, count); }

 public:
  OutputString(string& str) : OutputDevice(), str(str) {}
  ~OutputString() override { flush(); }
};
unique_ptr<InputFile> input;
unique_ptr<OutputFile> output;
inline int read(Detail::Base base) {
  input->base = base.value;
  return 0;
}
inline int read() { return 0; }
inline int read(char& arg) { return input->readChar(arg); }
template <class I>
inline typename enable_if<is_integral<I>::value && is_unsigned<I>::value,
                          int>::type
read(I& arg) {
  return input->readUnsignedInt(arg);
}
template <class I>
inline
    typename enable_if<is_integral<I>::value && is_signed<I>::value, int>::type
    read(I& arg) {
  return input->readSignedInt(arg);
}
template <class F>
inline typename enable_if<is_floating_point<F>::value, int>::type read(F& arg) {
  return input->readFloatingPoint(arg);
}
inline int read(const char& arg) {
  input->skipCharacters([arg](char c) { return arg != c; });
  return 0;
}
inline int read(const char* arg) {
  if (*arg)
    input->skipCharacters(
        [arg](char c) { return InputDevice::isOneOf(c, arg); });
  else
    input->skipCharacters();
  input->putBack();
  return 0;
}
inline int read(bool (*isSkipped)(char)) {
  input->skipCharacters(isSkipped);
  input->putBack();
  return 0;
}
template <class... Ts>
int read(char* arg, int limit, bool (*isTerminator)(char), Ts&&... args);
template <class... Ts>
int read(char* arg, int limit, const char* terminators, Ts&&... args);
template <class Iterator, class... Ts,
          typename = decltype(*std::declval<Iterator>())>
int read(Iterator first, Iterator last, Ts&&... args);
template <class Iterator, class... Ts,
          typename = decltype(*std::declval<Iterator>())>
int read(Iterator first, int count, Ts&&... args);
template <class T0, class T1, class... Ts,
          typename =
              typename enable_if<!is_convertible<T0, char*>::value, void>::type>
int read(T0&& arg0, T1&& arg1, Ts&&... args);
inline int read(char* arg, int limit, const char* terminators = "") {
  if (!*terminators)
    return input->readString(arg, limit, InputDevice::isSpace);
  else
    return input->readString(arg, limit, [terminators](char c) {
      return InputDevice::isOneOf(c, terminators);
    });
}
template <class... Ts>
inline int read(char* first, char* last, Ts&&... args) {
  return read(first, static_cast<int>(last - first), forward<Ts>(args)...);
}
template <int N, class... Ts>
inline int read(char (&arg)[N], Ts&&... args) {
  return read(static_cast<char*>(arg), N, forward<Ts>(args)...);
}
template <class... Ts>
inline int read(char* arg, int limit, bool (*isTerminator)(char),
                Ts&&... args) {
  int argsRead = input->readString(arg, limit, isTerminator);
  return argsRead + read(forward<Ts>(args)...);
}
template <class... Ts>
inline int read(char* arg, int limit, const char* terminators, Ts&&... args) {
  int argsRead = read(arg, limit, terminators);
  return argsRead + read(forward<Ts>(args)...);
}
template <class T1, class T2>
inline int read(pair<T1, T2>& arg) {
  return read(arg.first) == 1 && read(arg.second) == 1 ? 1 : 0;
}
template <class T>
inline int read(vector<T>& arg) {
  uint n;
  if (read(n) == 0) return 0;
  arg.resize(n);
  return read(arg.begin(), arg.end());
}
template <class Iterator, class... Ts, typename>
int read(Iterator first, Iterator last, Ts&&... args) {
  int success = 1;
  for (; first != last; ++first) success &= read(*first);
  return success + read(forward<Ts>(args)...);
}
template <class Iterator, class... Ts, typename>
int read(Iterator first, int count, Ts&&... args) {
  return read(first, first + count, forward<Ts>(args)...);
}
template <class T0, class T1, class... Ts, typename>
inline int read(T0&& arg0, T1&& arg1, Ts&&... args) {
  int argsRead = read(forward<T0>(arg0));
  return argsRead + read(forward<T1>(arg1), forward<Ts>(args)...);
}
inline int write(Detail::Width width) {
  output->width = static_cast<int>(width.value);
  return 0;
}
inline int write(Detail::Fill fill) {
  output->fill = fill.value;
  return 0;
}
inline int write(Detail::Base base) {
  output->base = base.value;
  output->computeBasePower();
  return 0;
}
inline int write(Detail::Precision precision) {
  output->precision = precision.value;
  output->computeBasePower();
  return 0;
}
inline int write(Detail::Delimiter delimiter) {
  output->delimiter = delimiter.value;
  return 0;
}
inline int write() { return 0; }
inline int write(char arg) { return output->writeChar(arg); }
template <class I>
inline typename enable_if<is_integral<I>::value && is_unsigned<I>::value,
                          int>::type
write(I arg) {
  return output->writeUnsignedInt(arg);
}
template <class I>
inline
    typename enable_if<is_integral<I>::value && is_signed<I>::value, int>::type
    write(I arg) {
  return output->writeSignedInt(arg);
}
template <class F>
inline typename enable_if<is_floating_point<F>::value, int>::type write(F arg) {
  return output->writeFloatingPoint(arg);
}
inline int write(const char* arg) {
  return output->writeString(arg, static_cast<int>(strlen(arg)));
}
template <int N>
inline int write(char (&arg)[N]) {
  return output->writeString(arg, static_cast<int>(strlen(arg)));
}
inline int write(const string& arg) {
  return output->writeString(arg.c_str(), static_cast<int>(arg.size()));
}
template <class T1, class T2>
inline int write(const pair<T1, T2>& arg) {
  int charsWritten = write(arg.first);
  charsWritten += output->writeDelimiter();
  return charsWritten + write(arg.second);
}
template <
    class Iterator, class... Ts,
    typename = typename enable_if<!is_convertible<Iterator, const char*>::value,
                                  decltype(*std::declval<Iterator>())>::type>
int write(Iterator first, Iterator last, Ts&&... args);
template <
    class Iterator, class... Ts,
    typename = typename enable_if<!is_convertible<Iterator, const char*>::value,
                                  decltype(*std::declval<Iterator>())>::type>
int write(Iterator first, int count, Ts&&... args);
template <class T, class T2, class... Ts>
int write(T&& arg, T2&& arg2, Ts&&... args);
template <class Iterator, class... Ts, typename>
int write(Iterator first, Iterator last, Ts&&... args) {
  int charsWritten = 0;
  for (; first != last;
       charsWritten += ++first == last ? 0 : output->writeDelimiter())
    charsWritten += write(*first);
  return charsWritten + write(forward<Ts>(args)...);
}
template <class Iterator, class... Ts, typename>
int write(Iterator first, int count, Ts&&... args) {
  return write(first, first + count, forward<Ts>(args)...);
}
template <class T, class T2, class... Ts>
inline int write(T&& arg, T2&& arg2, Ts&&... args) {
  int charsWritten = write(forward<T>(arg));
  return charsWritten + write(forward<T2>(arg2), forward<Ts>(args)...);
}
template <class... Ts>
inline int writeln(Ts&&... args) {
  return write(forward<Ts>(args)..., '\n');
}
void flush() { output->flush(); }
vector<vector<int>> e;
vector<int> p;
int h;
int query(int v) {
  int k;
  writeln("? ", v);
  flush();
  read(k);
  if (k == 0) exit(0);
  p.push_back(v);
  e[v].resize(k);
  read((e[v]).begin(), (e[v]).end());
  if (k == 2) {
    writeln("! ", v);
    flush();
  }
  return k;
}
bool find1(int v, int forb, bool first = false) {
  int k = query(v);
  if (k == 1) return false;
  if (k == 2) return true;
  if (!first && (h >= 6 && static_cast<int>((p).size()) == 2 * h - 5)) {
    p.push_back(-1);
    p.push_back(-1);
    return false;
  }
  for (int u : e[v])
    if (u != forb) return find1(u, v, first);
  return false;
}
void solve() {
  e.assign(1 << h, vector<int>());
  p.clear();
  if (find1(1, -1, true)) return;
  reverse((p).begin(), (p).end());
  int v = p.back();
  if (static_cast<int>((e[v]).size()) != 1) {
    for (int u : e[v])
      if (u != p[static_cast<int>((p).size()) - 2]) {
        if (find1(u, v)) return;
        break;
      }
  }
  while (true) {
    int m = static_cast<int>((p).size()) / 2;
    v = p[m];
    vector<int> forb;
    if (m != 0) forb = {p[m - 1], p[m + 1]};
    p.erase(p.begin() + m + 1, p.end());
    if (static_cast<int>((p).size()) == h - 3) {
      for (int u : e[v])
        if (find((forb).begin(), (forb).end(), u) == forb.end()) {
          int k = query(u);
          if (k == 2) return;
          vector<int> c;
          for (int x : e[u])
            if (x != v) {
              k = query(x);
              if (k == 2) return;
              for (int y : e[x])
                if (y != u) c.push_back(y);
            }
          for (int i(0), b_(static_cast<int>((c).size()) - 1); i < b_; ++i)
            if (query(c[i]) == 2) return;
          writeln("! ", c.back());
          flush();
          return;
        }
    }
    for (int u : e[v])
      if (find((forb).begin(), (forb).end(), u) == forb.end()) {
        if (static_cast<int>((p).size()) == h - 1) {
          writeln("! ", u);
          flush();
          return;
        } else if (static_cast<int>((p).size()) == h - 2) {
          int k = query(u);
          if (k == 3) {
            vector<int> c;
            for (int x : e[u])
              if (x != v) c.push_back(x);
            if (query(c[0]) != 2) {
              writeln("! ", c[1]);
              flush();
            }
          }
          return;
        } else if (find1(u, v))
          return;
      }
  }
}
int main() {
  input.reset(new InputFile());
  output.reset(new OutputFile());
  int t;
  read(t);
  for (int it(0), b_(t); it < b_; ++it) {
    read(h);
    if (h == 0) return 0;
    solve();
  }
  return 0;
}

```