Problem: This is the easy version of the problem. The difference between the versions is the constraint on n and the required number of operations. You can make hacks only if all versions of the problem are solved.

There are two binary strings a and b of length n (a binary string is a string consisting of symbols 0 and 1). In an operation, you select a prefix of a, and simultaneously invert the bits in the prefix (0 changes to 1 and 1 changes to 0) and reverse the order of the bits in the prefix.

For example, if a=001011 and you select the prefix of length 3, it becomes 011011. Then if you select the entire string, it becomes 001001.

Your task is to transform the string a into b in at most 3n operations. It can be proved that it is always possible.

Input

The first line contains a single integer t (1≤ t≤ 1000) — the number of test cases. Next 3t lines contain descriptions of test cases.

The first line of each test case contains a single integer n (1≤ n≤ 1000) — the length of the binary strings.

The next two lines contain two binary strings a and b of length n.

It is guaranteed that the sum of n across all test cases does not exceed 1000.

Output

For each test case, output an integer k (0≤ k≤ 3n), followed by k integers p_1,…,p_k (1≤ p_i≤ n). Here k is the number of operations you use and p_i is the length of the prefix you flip in the i-th operation.

Example

Input


5
2
01
10
5
01011
11100
2
01
01
10
0110011011
1000110100
1
0
1


Output


3 1 2 1
6 5 2 5 3 1 2
0
9 4 1 2 10 4 1 2 1 5
1 1

Note

In the first test case, we have 01→ 11→ 00→ 10.

In the second test case, we have 01011→ 00101→ 11101→ 01000→ 10100→ 00100→ 11100.

In the third test case, the strings are already the same. Another solution is to flip the prefix of length 2, which will leave a unchanged.

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import static java.util.Collections.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class cfa {

    @SuppressWarnings("unused")
    private static final int MOD = (int) (1e9 + 7), MOD_FFT = 998244353;
    private static final Reader r = new Reader();
    private static final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
    private static final boolean thread = false;
    private static final boolean HAS_TEST_CASES = true;
    private static final int SCAN_LINE_LENGTH = 131074;

    static int n, a[], e[][], vis[];
    private static ArrayList<Integer> adj[], topo;

    static void solve() throws Exception {
        int n = ni();
        char[] a = n().toCharArray(), b = n().toCharArray();
        ArrayList<Integer> ans = new ArrayList<>();
        // int c0 = 0, ci = 0, j = 0;
        for (int i = n - 1; i > -1; --i) {
            char ch0 = a[0], ch = a[i];
            if (ch == b[i])
                continue;
            if (i == 0) {
                if (ch0 != b[i])
                    ans.add(1);
                continue;
            }
            if (ch0 == b[i]) {
                // ci++;
                a = rev(a, 0);
                a = rev(a, i);
                ans.add(1);
                ans.add(i + 1);
                // j++;
            } else {
                a = rev(a, i);
                // c0++;
                // ci++;
                ans.add(i + 1);
                // j++;
            }

        }
        p(ans.size() + " ");
        for (Integer i : ans) {
            p(i + " ");
        }
        pn();
    }

    private static char[] rev(char[] a, int j) {
        int i = 0,   n  = j;
        while (i < j) {
            char t = a[i];
            a[i] = a[j];
            a[j] = t;
            a[i] = (a[i] == '0') ? '1' : '0';
            a[j] = (a[j] == '0') ? '1' : '0';
            i++;
            j--;
        }
        if (n % 2 == 0)
            a[i] = (a[i] == '0') ? '1' : '0';
        return a;
    }

    public static void main(final String[] args) throws Exception {
        if (!thread) {
            final int testcases = HAS_TEST_CASES ? ni() : 1;
            for (int i = 1; i <= testcases; i++) {
                // out.print("Case #" + (i + 1) + ": ");
                try {
                    solve();
                } catch (final Exception e) {
                    pni("idk Exception");
                    e.printStackTrace(System.err);
                    System.exit(0);
                }
            }
            out.flush();
            r.close();
            out.close();
        }
    }

    @SuppressWarnings("unused")
    private static void swap(final int i, final int j) {
        final int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    @SuppressWarnings("unused")
    private static int gcd(final int a, final int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    @SuppressWarnings("unused")
    private static class Pair<T, E> implements Comparable<Pair<T, E>> {
        T fir;
        E snd;

        Pair() {
        }

        Pair(final T x, final E y) {
            this.fir = x;
            this.snd = y;
        }

        @Override
        @SuppressWarnings("unchecked")
        public int compareTo(final Pair<T, E> o) {
            final int c = ((Comparable<T>) fir).compareTo(o.fir);
            return c != 0 ? c : ((Comparable<E>) snd).compareTo(o.snd);
        }

    }

    @SuppressWarnings("unused")
    private static class pi implements Comparable<pi> {
        int fir, snd;

        pi() {
        }

        pi(final int a, final int b) {
            fir = a;
            snd = b;
        }

        public int compareTo(final pi o) {
            return fir == o.fir ? snd - o.snd : fir - o.fir;
        }

    }

    @SuppressWarnings("unused")
    private static <T> void checkV(final ArrayList<T> adj[], final int i) {
        adj[i] = adj[i] == null ? new ArrayList<>() : adj[i];
    }

    @SuppressWarnings("unused")
    private static <T> void checkV(final Vector<T> adj[], final int i) {
        adj[i] = adj[i] == null ? new Vector<>() : adj[i];
    }

    @SuppressWarnings("unused")
    private static int[] na(final int n) throws Exception {
        final int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = ni();
        }
        return a;
    }

    @SuppressWarnings("unused")
    private static int[] na1(final int n) throws Exception {
        final int[] a = new int[n + 1];
        for (int i = 1; i < a.length; i++) {
            a[i] = ni();
        }
        return a;
    }

    @SuppressWarnings("unused")
    private static String n() throws IOException {
        return r.readToken();
    }

    @SuppressWarnings("unused")
    private static String nln() throws IOException {
        return r.readLine();
    }

    private static int ni() throws IOException {
        return r.nextInt();
    }

    @SuppressWarnings("unused")
    private static long nl() throws IOException {
        return r.nextLong();
    }

    @SuppressWarnings("unused")
    private static double nd() throws IOException {
        return r.nextDouble();
    }

    @SuppressWarnings("unused")
    private static void p(final Object o) {
        out.print(o);
    }

    @SuppressWarnings("unused")
    private static void pn(final Object o) {
        out.println(o);
    }

    @SuppressWarnings("unused")
    private static void pn() {
        out.println("");
    }

    private static void pni(final Object o) {
        out.println(o);
        out.flush();
    }

    private static class Reader {
        private final int BUFFER_SIZE = 1 << 22;
        private final DataInputStream din;
        private final byte[] buffer;
        private int bufferPointer, bytesRead;
        // private StringTokenizer st;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        @SuppressWarnings("unused")
        public Reader(final String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        final byte[] buf = new byte[SCAN_LINE_LENGTH];

        public String readLine() throws IOException {
            int cnt = 0;
            int c;
            o: while ((c = read()) != -1) {
                if (c == '\n')
                    if (cnt == 0)
                        continue o;
                    else
                        break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public String readToken() throws IOException {
            int cnt = 0;
            int c;
            o: while ((c = read()) != -1) {
                if (!(c >= 33 && c <= 126))
                    if (cnt == 0)
                        continue o;
                    else
                        break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            final boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            final boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            final boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }

    static {
        if (thread)
            new Thread(null, new Runnable() {
                @Override
                public void run() {
                    try {
                        final int testcases = HAS_TEST_CASES ? ni() : 1;
                        for (int i = 1; i <= testcases; i++) {
                            // out.print("Case #" + (i + 1) + ": ");
                            try {
                                solve();
                            } catch (final Exception e) {
                                e.printStackTrace(System.err);
                                System.exit(-1);
                            }
                        }
                        out.flush();
                        r.close();
                        out.close();
                    } catch (final Throwable t) {
                        t.printStackTrace(System.err);
                        System.exit(-1);
                    }
                }
            }, "rec", (1L << 28)).start();
    }

    @SuppressWarnings({ "unchecked", "unused" })
    private static <T> T deepCopy(final T old) {
        try {
            return (T) deepCopyObject(old);
        } catch (final IOException | ClassNotFoundException e) {
            e.printStackTrace(System.err);
            System.exit(-1);
        }
        return null;
    }

    private static Object deepCopyObject(final Object oldObj) throws IOException, ClassNotFoundException {
        ObjectOutputStream oos = null;
        ObjectInputStream ois = null;
        try {
            final ByteArrayOutputStream bos = new ByteArrayOutputStream(); // A
            oos = new ObjectOutputStream(bos); // B
            // serialize and pass the object
            oos.writeObject(oldObj); // C
            oos.flush(); // D
            final ByteArrayInputStream bin = new ByteArrayInputStream(bos.toByteArray()); // E
            ois = new ObjectInputStream(bin); // F
            // return the new object
            return ois.readObject(); // G
        } catch (final ClassNotFoundException e) {
            pni("Exception in ObjectCloner = " + e);
            throw (e);
        } finally {
            oos.close();
            ois.close();
        }
    }

}