#include <bits/stdc++.h>

#define forn(i, n) for (int (i) = 0; (i) < int(n); ++(i))

using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii = std::pair<int, int>;
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define pb push_back

template<typename T>
static inline T gcd(T a, T b) {
    a = std::abs(a);
    b = std::abs(b);
    while (b > 0) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

template<typename T>
static inline T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

template<typename T>
static inline T sqr(T a) {
    return a * a;
}

template<typename T>
static inline bool remin(T &a, const T &val) {
    if (a > val) {
        a = val;
        return true;
    }
    return false;
}

template<typename T>
static inline bool remax(T &a, const T &val) {
    if (a < val) {
        a = val;
        return true;
    }
    return false;
}

static inline ll nxt() {
    int64_t x;
    scanf("%" PRId64, &x);
    return x;
}

static inline void skipEndLine() {
    char c = getchar();
    while (c != '\n') {
        c = getchar();
    }
}

static inline std::string nxtLine() {
    std::string ret;
    char c = '\n';
    while (true) {
        c = getchar();
        if (c == '\n' || c == '\r' || c == -1) {
            break;
        }
        ret.push_back(c);
    }
    return ret;
}

static inline std::string nxtString() {
    std::string ret;
    char c = '\n';
    while (true) {
        c = getchar();
        if (!isspace(c)) {
            break;
        }
    }
    if (c == -1) {
        return ret;
    }
    ret.push_back(c);
    while (true) {
        c = getchar();
        if (isspace(c) || c == -1) {
            break;
        }
        ret.push_back(c);
    }
    return ret;
}

static std::chrono::system_clock::time_point clock_t0;

static inline void init_time() {
    clock_t0 = std::chrono::system_clock::now();
}

static inline double get_time() {
    auto t = std::chrono::system_clock::now();
    return std::chrono::duration<double>((t - clock_t0)).count();
}

static inline void print_time(const std::string &name) {
    std::cerr << name << " " << get_time() << "s." << std::endl;
}

template <class T>
static inline T pw(T a, ll n) {
    T ret = T(1);
    while (n > 0) {
        if (n & 1) ret = ret * a;
        a = a * a;
        n >>= 1;
    }
    return ret;
}

static inline ll pw(ll a, ll n, ll m) {
//    if (a == 0) return 0;
    a %= m;
    ll ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return ret;
}

typedef std::thread thread_type;

class ThreadPool {
public:
    ThreadPool(size_t);

    template<class F, class... Args>
    auto enqueue(F &&f, Args &&... args)
    -> std::future<typename std::result_of<F(Args...)>::type>;

    ~ThreadPool();

private:
    // need to keep track of threads so we can join them
    std::vector<thread_type> workers;
    // the task queue
    std::queue<std::function<void()> > tasks;

    // synchronization
    std::mutex queue_mutex;
    std::condition_variable condition;
    bool stop;
};

// the constructor just launches some amount of workers
inline ThreadPool::ThreadPool(size_t threads)
        : stop(false) {
    for (size_t i = 0; i < threads; ++i) {
        auto f = [this] {
            for (;;) {
                std::function<void()> task;

                {
                    std::unique_lock<std::mutex> lock(this->queue_mutex);
                    this->condition.wait(lock,
                                         [this] { return this->stop || !this->tasks.empty(); });
                    if (this->stop && this->tasks.empty())
                        return;
                    task = std::move(this->tasks.front());
                    this->tasks.pop();
                }

                task();
            }
        };
        workers.emplace_back(f);
    }
}

// add new work item to the pool
template<class F, class... Args>
auto ThreadPool::enqueue(F &&f, Args &&... args) -> std::future<typename std::result_of<F(Args...)>::type> {
    using return_type = typename std::result_of<F(Args...)>::type;

    auto task = std::make_shared<std::packaged_task<return_type()> >(
            std::bind(std::forward<F>(f), std::forward<Args>(args)...)
    );

    std::future<return_type> res = task->get_future();
    {
        std::unique_lock<std::mutex> lock(queue_mutex);

        // don't allow enqueueing after stopping the pool
        if (stop) {
            throw std::runtime_error("enqueue on stopped ThreadPool");
        }

        tasks.emplace([task]() { (*task)(); });
    }
    condition.notify_one();
    return res;
}

// the destructor joins all threads
inline ThreadPool::~ThreadPool() {
    {
        std::unique_lock<std::mutex> lock(queue_mutex);
        stop = true;
    }
    condition.notify_all();
    for (thread_type &worker: workers) {
        worker.join();
    }
}

static const ld PI = acosl(-1.0);
static std::mt19937_64 generator{123123123};

using namespace std;

void prepare() {

}

static const ll mod = 998244353;

int query(int l1, int r1, int l2, int r2) {
    if (l1 >= r1) return 0;
    if (l2 >= r2) return 0;

    cout << "? " << (r1 - l1) << " " << (r2 - l2) << "\n";
    for (int i = l1; i < r1; ++i) {
        cout << i + 1 << " ";
    }
    cout << "\n";
    for (int i = l2; i < r2; ++i) {
        cout << i + 1 << " ";
    }
    cout << endl;
    int v;
    cin >> v;
    return v;
}

void solve(int test) {
    int n;
    cin >> n;
    int p = 1;
    while (p + 1 < n) {
        int v = query(0, p, p, p + 1);
        if (v != 0) {
            break;
        }
        ++p;
    }
    vector<int> ans(n, 0);
    ans[p] = 1;
    for (int i = p + 1; i < n; ++i) {
        int v = query(p, p + 1, i, i + 1);
        if (v != 0) {
            ans[i] = 1;
        }
    }
    int l = 0, r = p - 1;
    while (l < r) {
        int m = (l + r + 1) >> 1;
        int v = query(m, p, p, p + 1);
        if (v != 0) {
            l = m;
        } else {
            r = m - 1;
        }
    }
    ans[l] = 1;
    int cnt = 0;
    forn(i, n) {
        cnt += int(ans[i] == 0);
    }
    cout << "! " << cnt;
    forn(i, n) {
        if (ans[i] == 0) {
            cout << " " << i + 1;
        }
    }
    cout << endl;
}

int main() {
#ifdef LOCAL
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    init_time();

    prepare();
    int t = 1;
//    t = nxt();
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve(i + 1);
    }

    print_time("Time:");
    return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

This is an interactive problem.

Kochiya Sanae is playing with magnets. Realizing that some of those magnets are demagnetized, she is curious to find them out.

There are n magnets, which can be of the following 3 types:

  * N
  * S
  * - — these magnets are demagnetized.



Note that you don't know the types of these magnets beforehand.

You have a machine which can measure the force between the magnets, and you can use it at most n+⌊ log_2n⌋ times.

You can put some magnets to the left part of the machine and some to the right part of the machine, and launch the machine. Obviously, you can put one magnet to at most one side (you don't have to put all magnets). You can put the same magnet in different queries.

Then the machine will tell the force these magnets produce. Formally, let n_1,s_1 be the number of N and S magnets correspondently on the left and n_2,s_2 — on the right. Then the force between them would be n_1n_2+s_1s_2-n_1s_2-n_2s_1. Please note that the force is a signed value.

However, when the absolute value of the force is strictly larger than n, the machine will crash into pieces.

You need to find all magnets of type - (all demagnetized ones), without breaking the machine.

Note that the interactor is not adaptive. The types of the magnets are fixed before the start of the interaction and do not change with queries.

It is guaranteed that there are at least 2 magnets whose type is not -, and at least 1 magnet of type -.

Input

The first line contains a single integer t (1 ≤ t ≤ 100) — the number of test cases.

Interaction

For each test case you should start by reading an integer n (3 ≤ n ≤ 2000) — the number of the magnets. 

It is guaranteed that the total sum of all n over all test cases doesn't exceed 2000.

After that you can put some magnets into the machine and make a query from the statement.

You have to print each query in three lines:

  * In the first line print "? l r" (without quotes) where l and r (1 ≤ l,r < n, l+r ≤ n) respectively denote the number of the magnets you put to left and right.
  * In the second line print l integers a_1, ..., a_l (1 ≤ a_i ≤ n, a_i ≠ a_j if i ≠ j) — the indices of the magnets you put to left.
  * In the third line print r integers b_1, ..., b_r (1 ≤ b_i ≤ n, b_i ≠ b_j if i ≠ j) — the indices of the magnets you put to right.
  * The same magnet can't be put to both sides in the same query. Formally, you should guarantee that a_i ≠ b_j for any i and j. However, you may leave some magnets unused.



After printing a query do not forget to output end of line and flush the output. To do this, use:

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



After this, you should read an integer F — the force these magnets produce.

Note that if your query is invalid(either the query limit exceeds, the machine crashes or the arguments are invalid), the interactor will terminate immediately. In this case terminate your program to receive verdict Wrong Answer instead of arbitrary verdicts.

If you are confident about your answer, use the following format to report it:

  * "! k A", where k is the number of magnets you found, and A is an array consisting of k different integers from 1 to n denoting the indices of the magnets of type - that you found. You may print elements of A in arbitrary order.
  * After that, if this is the last test case, you have to terminate your program; otherwise you should immediately continue to deal with the next test case.



Note that the interactor is not adaptive. The types of the magnets are fixed before the start of interaction and do not change with queries.

Hacks

To hack a solution, use the following format:

The first line contains a single integer t (1 ≤ t ≤ 100) — the number of test cases in your hack.

Then follow the descriptions of the t test cases, each printed in two lines:

  * The first line contains a single integer n (3 ≤ n ≤ 2000) — the number of magnets.
  * The second line contains a string S of length n consisting of only N, S and -, denoting the magnets' types.
  * Each of your test case should guarantee that there are at least 2 magnets whose type is not -, and at least 1 magnet of type -. Meanwhile, the total sum of n in all test cases should not exceed 2000.

Example

Input


1
4



0



1



0



0



Output




? 1 1
3
4

? 1 2
1
2 3

? 1 1
1
4

? 1 1
1
3

! 2 3 4

Note

The empty lines in the sample are just for you to better understand the interaction process. You're not required to print them.

In the sample, the types of the magnets are NN--.

At first, you put the third magnet on the left and the fourth one on the right. Both of them have type -, thus no force is produced.

Then you put the first magnet on the left and the second and third one on the right. The third magnet has type -, while the other two magnets are of type N, so the force produced is 1.

In the following two queries, the force is 0 since there is only a magnet with property - on the right.

Then we can determine that the magnets of type - are the third and the fourth one, so we should print ! 2 3 4 and exit.

### Response

```cpp
#include <bits/stdc++.h>

#define forn(i, n) for (int (i) = 0; (i) < int(n); ++(i))

using ll=long long;
using ull=unsigned long long;
using ld=long double;
using pii = std::pair<int, int>;
#define x first
#define y second
#define all(x) (x).begin(),(x).end()
#define pb push_back

template<typename T>
static inline T gcd(T a, T b) {
    a = std::abs(a);
    b = std::abs(b);
    while (b > 0) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

template<typename T>
static inline T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}

template<typename T>
static inline T sqr(T a) {
    return a * a;
}

template<typename T>
static inline bool remin(T &a, const T &val) {
    if (a > val) {
        a = val;
        return true;
    }
    return false;
}

template<typename T>
static inline bool remax(T &a, const T &val) {
    if (a < val) {
        a = val;
        return true;
    }
    return false;
}

static inline ll nxt() {
    int64_t x;
    scanf("%" PRId64, &x);
    return x;
}

static inline void skipEndLine() {
    char c = getchar();
    while (c != '\n') {
        c = getchar();
    }
}

static inline std::string nxtLine() {
    std::string ret;
    char c = '\n';
    while (true) {
        c = getchar();
        if (c == '\n' || c == '\r' || c == -1) {
            break;
        }
        ret.push_back(c);
    }
    return ret;
}

static inline std::string nxtString() {
    std::string ret;
    char c = '\n';
    while (true) {
        c = getchar();
        if (!isspace(c)) {
            break;
        }
    }
    if (c == -1) {
        return ret;
    }
    ret.push_back(c);
    while (true) {
        c = getchar();
        if (isspace(c) || c == -1) {
            break;
        }
        ret.push_back(c);
    }
    return ret;
}

static std::chrono::system_clock::time_point clock_t0;

static inline void init_time() {
    clock_t0 = std::chrono::system_clock::now();
}

static inline double get_time() {
    auto t = std::chrono::system_clock::now();
    return std::chrono::duration<double>((t - clock_t0)).count();
}

static inline void print_time(const std::string &name) {
    std::cerr << name << " " << get_time() << "s." << std::endl;
}

template <class T>
static inline T pw(T a, ll n) {
    T ret = T(1);
    while (n > 0) {
        if (n & 1) ret = ret * a;
        a = a * a;
        n >>= 1;
    }
    return ret;
}

static inline ll pw(ll a, ll n, ll m) {
//    if (a == 0) return 0;
    a %= m;
    ll ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return ret;
}

typedef std::thread thread_type;

class ThreadPool {
public:
    ThreadPool(size_t);

    template<class F, class... Args>
    auto enqueue(F &&f, Args &&... args)
    -> std::future<typename std::result_of<F(Args...)>::type>;

    ~ThreadPool();

private:
    // need to keep track of threads so we can join them
    std::vector<thread_type> workers;
    // the task queue
    std::queue<std::function<void()> > tasks;

    // synchronization
    std::mutex queue_mutex;
    std::condition_variable condition;
    bool stop;
};

// the constructor just launches some amount of workers
inline ThreadPool::ThreadPool(size_t threads)
        : stop(false) {
    for (size_t i = 0; i < threads; ++i) {
        auto f = [this] {
            for (;;) {
                std::function<void()> task;

                {
                    std::unique_lock<std::mutex> lock(this->queue_mutex);
                    this->condition.wait(lock,
                                         [this] { return this->stop || !this->tasks.empty(); });
                    if (this->stop && this->tasks.empty())
                        return;
                    task = std::move(this->tasks.front());
                    this->tasks.pop();
                }

                task();
            }
        };
        workers.emplace_back(f);
    }
}

// add new work item to the pool
template<class F, class... Args>
auto ThreadPool::enqueue(F &&f, Args &&... args) -> std::future<typename std::result_of<F(Args...)>::type> {
    using return_type = typename std::result_of<F(Args...)>::type;

    auto task = std::make_shared<std::packaged_task<return_type()> >(
            std::bind(std::forward<F>(f), std::forward<Args>(args)...)
    );

    std::future<return_type> res = task->get_future();
    {
        std::unique_lock<std::mutex> lock(queue_mutex);

        // don't allow enqueueing after stopping the pool
        if (stop) {
            throw std::runtime_error("enqueue on stopped ThreadPool");
        }

        tasks.emplace([task]() { (*task)(); });
    }
    condition.notify_one();
    return res;
}

// the destructor joins all threads
inline ThreadPool::~ThreadPool() {
    {
        std::unique_lock<std::mutex> lock(queue_mutex);
        stop = true;
    }
    condition.notify_all();
    for (thread_type &worker: workers) {
        worker.join();
    }
}

static const ld PI = acosl(-1.0);
static std::mt19937_64 generator{123123123};

using namespace std;

void prepare() {

}

static const ll mod = 998244353;

int query(int l1, int r1, int l2, int r2) {
    if (l1 >= r1) return 0;
    if (l2 >= r2) return 0;

    cout << "? " << (r1 - l1) << " " << (r2 - l2) << "\n";
    for (int i = l1; i < r1; ++i) {
        cout << i + 1 << " ";
    }
    cout << "\n";
    for (int i = l2; i < r2; ++i) {
        cout << i + 1 << " ";
    }
    cout << endl;
    int v;
    cin >> v;
    return v;
}

void solve(int test) {
    int n;
    cin >> n;
    int p = 1;
    while (p + 1 < n) {
        int v = query(0, p, p, p + 1);
        if (v != 0) {
            break;
        }
        ++p;
    }
    vector<int> ans(n, 0);
    ans[p] = 1;
    for (int i = p + 1; i < n; ++i) {
        int v = query(p, p + 1, i, i + 1);
        if (v != 0) {
            ans[i] = 1;
        }
    }
    int l = 0, r = p - 1;
    while (l < r) {
        int m = (l + r + 1) >> 1;
        int v = query(m, p, p, p + 1);
        if (v != 0) {
            l = m;
        } else {
            r = m - 1;
        }
    }
    ans[l] = 1;
    int cnt = 0;
    forn(i, n) {
        cnt += int(ans[i] == 0);
    }
    cout << "! " << cnt;
    forn(i, n) {
        if (ans[i] == 0) {
            cout << " " << i + 1;
        }
    }
    cout << endl;
}

int main() {
#ifdef LOCAL
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    init_time();

    prepare();
    int t = 1;
//    t = nxt();
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve(i + 1);
    }

    print_time("Time:");
    return 0;
}

```