Problem: Carl has n coins of various colors, and he would like to sort them into piles. The coins are labeled 1,2,…,n, and each coin is exactly one of red, green, or blue. He would like to sort the coins into three different piles so one pile contains all red coins, one pile contains all green coins, and one pile contains all blue coins.

Unfortunately, Carl is colorblind, so this task is impossible for him. Luckily, he has a friend who can take a pair of coins and tell Carl if they are the same color or not. Using his friend, Carl believes he can now sort the coins. The order of the piles doesn't matter, as long as all same colored coins are in the one pile, and no two different colored coins are in the same pile.

His friend will answer questions about multiple pairs of coins in batches, and will answer about all of those pairs in parallel. Each coin should be in at most one pair in each batch. The same coin can appear in different batches.

Carl can use only 7 batches. Help him find the piles of coins after sorting.

Interaction

You will be given multiple test cases. The first line contains an integer t (1 ≤ t ≤ 5) — the number of test cases.

The first line of each test case contains one integer n (1 ≤ n ≤ 10^5) — the number of coins. If you read in a value of -1 here, that means that you printed an invalid answer in the previous case and exit immediately to avoid getting other verdicts.

To ask a question, print "Q k\ x_1\ y_1\ …\ x_k\ y_k" (1 ≤ k ≤ n/2, 1 ≤ x_i,y_i ≤ n, x_i ≠ y_i). k denotes the number of pairs in the batch, and x_i, y_i denote the i-th pair of coins in the batch. A coin can only appear at most once in a batch. All x_i and y_i should be distinct.

The judge will respond with a bitstring of length k, where the i-th character is "1" if x_i and y_i are the same color, and "0" otherwise. The judge will respond with -1 if you ever ask an invalid query. Make sure to exit immediately to avoid getting other verdicts.

When you are ready to answer, print four lines.

The first line contains "A k_1\ k_2\ k_3" (0 ≤ k_1,k_2,k_3 and k_1+k_2+k_3 = n). These denote the sizes of the three piles.

The next line has k_1 integers, the labels of the coins in the first pile.

The next line has k_2 integers, the labels of the coins in the second pile.

The next line has k_3 integers, the labels coins in the third pile.

Each coin must appear in exactly one pile.

You may only ask at most 7 batches per test case.

After printing a query and the answer do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. 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.



Hack Format

To hack, use the following format. Note that you can only hack with one test case.

The first line should contain a single integer t (t=1).

The second line should contain a single string s consisting of only the characters "R", "G", "B" (1 ≤ |s| ≤ 10^5). The i-th character in this string represents the color of the i-th coin.

Example

Input


3
3
1
1
1
3
1
0
0
6
000
010
100
001
000


Output


Q 1 1 2
Q 1 2 3
Q 1 1 3
A 3 0 0
1 2 3


Q 1 1 3
Q 1 2 3
Q 1 1 2
A 2 0 1
1 3

2
Q 3 1 2 3 4 5 6
Q 3 1 3 2 5 4 6
Q 3 1 4 2 6 3 5
Q 3 1 5 2 4 3 6
Q 3 1 6 2 3 4 5
A 2 2 2
1 4
2 5
3 6

Note

In the example, there are three test cases.

In the first test case, there are three coins. We ask about the pairs (1,2), (2,3), and (1,3) in different batches and get that they are all the same color. Thus, we know all the coins are the same color, so we can put them all in one pile. Note that some piles can be empty and those are denoted with an empty line.

In the second test case, there are three coins again. This time, we only get that (1,3) are the same and (1,2) and (2,3) are different. So, one possible scenario is that coins 1 and 3 are red and coin 2 is green.

In the last case, there are 6 coins. The case shows how to ask and receive answers for multiple pairs in one batch.

Solution (in JAVA):

Solution:


import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.nio.charset.Charset;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CF1147E {
    public static void main(String[] args) throws Exception {
        boolean local = false;
        boolean async = false;

        Charset charset = Charset.forName("ascii");

        FastIO io = local ? new FastIO(new FileInputStream("D:\\DATABASE\\TESTCASE\\Code.in"), System.out, charset) : new FastIO(System.in, System.out, charset);
        Task task = new Task(io, new Debug(local));

        if (async) {
            Thread t = new Thread(null, task, "dalt", 1 << 27);
            t.setPriority(Thread.MAX_PRIORITY);
            t.start();
            t.join();
        } else {
            task.run();
        }

        if (local) {
            io.cache.append("\n\n--memory -- \n" + ((Runtime.getRuntime().totalMemory() - Runtime.getRuntime().freeMemory()) >> 20) + "M");
        }

        io.flush();
    }

    public static class Task implements Runnable {
        final FastIO io;
        final Debug debug;
        int inf = (int) 1e8;
        int mod = (int) 1e9 + 7;

        public int mod(int val) {
            val %= mod;
            if (val < 0) {
                val += mod;
            }
            return val;
        }

        public int mod(long val) {
            val %= mod;
            if (val < 0) {
                val += mod;
            }
            return (int) val;
        }

        int bitAt(int x, int i) {
            return (x >> i) & 1;
        }

        int bitAt(long x, int i) {
            return (int) ((x >> i) & 1);
        }

        public Task(FastIO io, Debug debug) {
            this.io = io;
            this.debug = debug;
        }

        @Override
        public void run() {
            int t = io.readInt();
            while (t-- > 0) {
                solve();
            }
        }

        public void solve() {
            int n = io.readInt();
            char[] ans = new char[n + 1];
            boolean[] isEqual = new boolean[n + 1];

            for (int k = 1; k <= 2; k++) {
                int count = 0;
                for (int i = k; i < n; i += 2) {
                    count++;
                }
                if (count == 0) {
                    continue;
                }
                io.cache.append("Q ");
                io.cache.append(count).append(' ');
                for (int i = k; i < n; i += 2) {
                    io.cache.append(i).append(' ').append(i + 1).append(' ');
                }
                io.cache.append('\n');
                io.flush();

                io.readString(ans, 0);

                for (int i = k, j = 0; i < n; i += 2, j++) {
                    isEqual[i] = ans[j] == '1';
                }
            }


            List<Node> list = new ArrayList<>();
            Node last = new Node();
            last.l = 1;
            for (int i = 1; i < n; i++) {
                if (isEqual[i]) {
                    continue;
                }
                last.r = i;
                list.add(last);
                last = new Node();
                last.l = i + 1;
            }
            last.r = n;
            list.add(last);

            int m = list.size();

            for (int k = 0; k < 4; k++) {
                int count = 0;
                for (int i = k; i + 2 < m; i += 4) {
                    count++;
                }
                if (count == 0) {
                    continue;
                }
                io.cache.append("Q ");
                io.cache.append(count).append(' ');
                for (int i = k; i + 2 < m; i += 4) {
                    io.cache.append(list.get(i).l).append(' ').append(list.get(i + 2).l).append(' ');
                }
                io.cache.append('\n');
                io.flush();

                io.readString(ans, 0);

                for (int i = k, j = 0; i + 2 < m; i += 4, j++) {
                    list.get(i).sameWithNext2 = ans[j] == '1';
                }
            }

            if (list.size() >= 1) {
                list.get(0).color = 0;
            }
            if (list.size() >= 2) {
                list.get(1).color = 1;
            }

            for (int i = 0; i + 2 < m; i++) {
                Node node = list.get(i);
                if (node.sameWithNext2) {
                    list.get(i + 2).color = list.get(i).color;
                } else {
                    list.get(i + 2).color = anotherColor(list.get(i).color, list.get(i + 1).color);
                }
            }

            int[] counts = new int[3];
            for (Node node : list) {
                counts[node.color] += node.r - node.l + 1;
            }

            io.cache.append("A ").append(counts[0]).append(' ').append(counts[1]).append(' ').append(counts[2]).append('\n');
            displayColor(list, 0);
            displayColor(list, 1);
            displayColor(list, 2);

            io.flush();
        }

        void displayColor(List<Node> list, int c) {
            for (Node node : list) {
                if (node.color != c) {
                    continue;
                }
                for (int i = node.l; i <= node.r; i++) {
                    io.cache.append(i).append(' ');
                }
            }
            io.cache.append('\n');
        }


        public int anotherColor(int a, int b) {
            if (a != 0 && b != 0) {
                return 0;
            }
            if (a != 1 && b != 1) {
                return 1;
            }
            return 2;
        }
    }

    public static class Node {
        int l;
        int r;
        boolean sameWithNext2;
        int color;
    }

    public static class FastIO {
        public final StringBuilder cache = new StringBuilder();
        private final InputStream is;
        private final OutputStream os;
        private final Charset charset;
        private StringBuilder defaultStringBuf = new StringBuilder(1 << 8);
        private byte[] buf = new byte[1 << 13];
        private int bufLen;
        private int bufOffset;
        private int next;

        public FastIO(InputStream is, OutputStream os, Charset charset) {
            this.is = is;
            this.os = os;
            this.charset = charset;
        }

        public FastIO(InputStream is, OutputStream os) {
            this(is, os, Charset.forName("ascii"));
        }

        private int read() {
            while (bufLen == bufOffset) {
                bufOffset = 0;
                try {
                    bufLen = is.read(buf);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (bufLen == -1) {
                    return -1;
                }
            }
            return buf[bufOffset++];
        }

        public void skipBlank() {
            while (next >= 0 && next <= 32) {
                next = read();
            }
        }

        public int readInt() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            int val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public long readLong() {
            int sign = 1;

            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+' ? 1 : -1;
                next = read();
            }

            long val = 0;
            if (sign == 1) {
                while (next >= '0' && next <= '9') {
                    val = val * 10 + next - '0';
                    next = read();
                }
            } else {
                while (next >= '0' && next <= '9') {
                    val = val * 10 - next + '0';
                    next = read();
                }
            }

            return val;
        }

        public double readDouble() {
            boolean sign = true;
            skipBlank();
            if (next == '+' || next == '-') {
                sign = next == '+';
                next = read();
            }

            long val = 0;
            while (next >= '0' && next <= '9') {
                val = val * 10 + next - '0';
                next = read();
            }
            if (next != '.') {
                return sign ? val : -val;
            }
            next = read();
            long radix = 1;
            long point = 0;
            while (next >= '0' && next <= '9') {
                point = point * 10 + next - '0';
                radix = radix * 10;
                next = read();
            }
            double result = val + (double) point / radix;
            return sign ? result : -result;
        }

        public String readString(StringBuilder builder) {
            skipBlank();

            while (next > 32) {
                builder.append((char) next);
                next = read();
            }

            return builder.toString();
        }

        public String readString() {
            defaultStringBuf.setLength(0);
            return readString(defaultStringBuf);
        }

        public int readLine(char[] data, int offset) {
            int originalOffset = offset;
            while (next != -1 && next != '\n') {
                data[offset++] = (char) next;
                next = read();
            }
            return offset - originalOffset;
        }

        public int readString(char[] data, int offset) {
            skipBlank();

            int originalOffset = offset;
            while (next > 32) {
                data[offset++] = (char) next;
                next = read();
            }

            return offset - originalOffset;
        }

        public int readString(byte[] data, int offset) {
            skipBlank();

            int originalOffset = offset;
            while (next > 32) {
                data[offset++] = (byte) next;
                next = read();
            }

            return offset - originalOffset;
        }

        public char readChar() {
            skipBlank();
            char c = (char) next;
            next = read();
            return c;
        }

        public void flush() {
            try {
                os.write(cache.toString().getBytes(charset));
                os.flush();
                cache.setLength(0);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public boolean hasMore() {
            skipBlank();
            return next != -1;
        }
    }

    public static class Debug {
        private boolean allowDebug;

        public Debug(boolean allowDebug) {
            this.allowDebug = allowDebug;
        }

        public void assertTrue(boolean flag) {
            if (!allowDebug) {
                return;
            }
            if (!flag) {
                fail();
            }
        }

        public void fail() {
            throw new RuntimeException();
        }

        public void assertFalse(boolean flag) {
            if (!allowDebug) {
                return;
            }
            if (flag) {
                fail();
            }
        }

        private void outputName(String name) {
            System.out.print(name + " = ");
        }

        public void debug(String name, int x) {
            if (!allowDebug) {
                return;
            }

            outputName(name);
            System.out.println("" + x);
        }

        public void debug(String name, long x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println("" + x);
        }

        public void debug(String name, double x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println("" + x);
        }

        public void debug(String name, int[] x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println(Arrays.toString(x));
        }

        public void debug(String name, long[] x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println(Arrays.toString(x));
        }

        public void debug(String name, double[] x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println(Arrays.toString(x));
        }

        public void debug(String name, Object x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println("" + x);
        }

        public void debug(String name, Object... x) {
            if (!allowDebug) {
                return;
            }
            outputName(name);
            System.out.println(Arrays.deepToString(x));
        }
    }
}