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.IOException;
import java.io.InputStream;
import java.util.*;

public class TestClass {


    static final class InputReader {
        private final InputStream stream;
        private final byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        private int read() throws IOException {
            if (curChar >= numChars) {
                curChar = 0;
                numChars = stream.read(buf);
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public final int readInt() throws IOException {
            return (int) readLong();
        }

        public final long readLong() throws IOException {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
                if (c == -1) throw new IOException();
            }
            boolean negative = false;
            if (c == '-') {
                negative = true;
                c = read();
            }
            long res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return negative ? -res : res;
        }

        public final int[] readIntArray(int size) throws IOException {
            int[] array = new int[size];
            for (int i = 0; i < size; i++) {
                array[i] = readInt();
            }
            return array;
        }

        public final long[] readLongArray(int size) throws IOException {
            long[] array = new long[size];
            for (int i = 0; i < size; i++) {
                array[i] = readLong();
            }
            return array;
        }

        public final String readString() throws IOException {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.append((char) c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
    }

    static long mulmod(long a, long b,
                       long mod) {
        long res = 0; // Initialize result
        a = a % mod;
        while (b > 0) {
            // If b is odd, add 'a' to result
            if (b % 2 == 1) {
                res = (res + a) % mod;
            }

            // Multiply 'a' with 2
            a = (a * 2) % mod;

            // Divide b by 2
            b /= 2;
        }

        // Return result
        return res % mod;
    }

    static long pow(long a, long b, long MOD) {
        long x = 1, y = a;
        while (b > 0) {
            if (b % 2 == 1) {
                x = (x * y);
                if (x > MOD) x %= MOD;
            }
            y = (y * y);
            if (y > MOD) y %= MOD;
            b /= 2;
        }
        return x;
    }

    static long[] f = new long[100001];

    static long InverseEuler(long n, long MOD) {
        return pow(n, MOD - 2, MOD);
    }

    static long C(int n, int r, long MOD) {

        return (f[n] * ((InverseEuler(f[r], MOD) * InverseEuler(f[n - r], MOD)) % MOD)) % MOD;
    }


    static int[] h = {0, 0, -1, 1};
    static int[] v = {1, -1, 0, 0};



    static class Pair2 {
        public long cost;
        int node;

        public Pair2(long cos, int node) {
            this.cost = cos;
            this.node = node;
        }
    }

    static long compute_hash(String s) {
        int p = 31;
        int m = 1000000007;
        long hash_value = 0;
        long p_pow = 1;
        for (int i = 0; i < s.length(); ++i) {
            char c = s.charAt(i);
            hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
            p_pow = (p_pow * p) % m;
        }
        return hash_value;
    }

    public static class SegmentTree {
        long[] tree;
        int n;

        public SegmentTree(int[] nodes) {
            tree = new long[nodes.length * 4];
            n = nodes.length;
            build(0, n - 1, 0, nodes);

        }

        private void build(int l, int r, int pos, int[] nodes) {
            if (l == r) {
                tree[pos] = nodes[l];
                return;
            }
            int mid = (l + r) / 2;
            build(l, mid, 2 * pos + 1, nodes);
            build(mid + 1, r, 2 * pos + 2, nodes);
            tree[pos] = tree[2 * pos + 1] + tree[2 * pos + 2];
        }

        public void update(int pos, int val) {
            updateUtil(0, n - 1, 0, pos, val);
        }

        public long get(int l, int r) {
            return getUtil(0, n - 1, 0, l, r);
        }

        private long getUtil(int l, int r, int pos, int ql, int qr) {
            if (ql > r || qr < l) {
                return 0;
            }
            if (l >= ql && r <= qr) {
                return tree[pos];
            }

            int mid = (l + r) / 2;
            return getUtil(l, mid, 2 * pos + 1, ql, qr) + getUtil(mid + 1, r, 2 * pos + 2, ql, qr);

        }

        private void updateUtil(int l, int r, int pos, int i, int val) {
            if (i < l || i > r) {
                return;
            }
            if (l == r) {
                tree[pos] = val;
                return;
            }
            int mid = (l + r) / 2;
            updateUtil(l, mid, 2 * pos + 1, i, val);
            updateUtil(mid + 1, r, 2 * pos + 2, i, val);
            tree[pos] = tree[2 * pos + 1] + tree[2 * pos + 2];
        }
    }

    static int counter = 0;
    static int[] rIn;
    static int[] rOut;
    static int[] lIn;
    static int[] lOut;
    private static int[] flatten;
    private static int[] lFlatten;
    static long answer = 0;

    static int VISITED = 1;
    static int VISITING = 2;

    public static void main(String[] args) throws Exception {
        //https://i...content-available-to-author-only...e.com/ebRGa6
        InputReader in = new InputReader(System.in);


        int t = in.readInt();

        while (t-- > 0) {
            int n = in.readInt();

            String a = in.readString();
            String b = in.readString();

            boolean[] aa = new boolean[n];
            boolean[] bb = new boolean[n];

            for (int i  =0; i < n; ++i) {
                if (a.charAt(i) == '1') {
                    aa[i] = true;
                }
            }
            for (int i  =0; i < n; ++i) {
                if (b.charAt(i) == '1') {
                    bb[i] = true;
                }
            }

            int startPos = 0;
            int endPos = n-1;
            int rotated = 0;
            List<Integer> ans = new ArrayList<>();

            for (int i = n-1; i >= 0; --i) {

//                System.out.println(startPos + "  " + endPos);
                boolean needsRotation = false;
                if (rotated % 2 == 0) {
                    if (aa[endPos] != bb[i]) needsRotation = true;
                } else {
                    if (aa[endPos] == bb[i]) needsRotation = true;
                }
                if (needsRotation) {
                    boolean needsReversal = false;
                    if (rotated % 2 == 0) {
                        if (aa[startPos] == bb[i]) needsReversal = true;
                    } else {
                        if (aa[startPos] != bb[i]) needsReversal = true;
                    }
                    if (needsReversal) {
                        ans.add(1);
                    }
                    ans.add(i + 1);
                    int temp = endPos;
                    if (rotated % 2 == 0) {
                        endPos = startPos + 1;
                    } else {
                        endPos = startPos - 1;
                    }
                    startPos = temp;

//                    System.out.println(startPos + " suck " + endPos);
                    rotated++;
                } else {
                    if (rotated % 2 == 0) {
                        endPos--;
                    } else
                        endPos++;
                }
            }
            System.out.print(ans.size() + " ");
            for (int i = 0; i < ans.size(); ++i) {
                System.out.print(ans.get(i) + " ");
            }
            System.out.println("");

         }





    }

    private static long solve(int pos, int curK, int k, int[] arr, int m, long[][] dp) {
        System.out.println(pos);
        if (pos == arr.length) {
            if (curK == k) return 0;
            return -1000000000000L;
        }

        if (curK > k) return -1000000000000L;

        if (dp[pos][curK] != -1) return dp[pos][curK];

        long with = -1000000000000L;
        if (curK < k)
            with = solve(pos + 1, curK + 1, k, arr, m, dp) + arr[pos] * (((curK + 1) % m));
        long without = solve(pos + 1, curK, k, arr, m, dp);

        return dp[pos][curK] = Math.max(with, without);
    }

    static int countFreq(String pattern, String text) {
        int m = pattern.length();
        int n = text.length();
        int res = 0;

        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break;
                }
            }
            if (j == m) {
                res++;
                j = 0;
            }
        }
        return res;
    }


    private static void dfsR(List<List<Integer>> g, int node, int[] v) {
        rIn[node] = counter;
        flatten[counter++] = v[node];

        for (int i = 0; i < g.get(node).size(); ++i) {
            dfsR(g, g.get(node).get(i), v);
        }

        rOut[node] = counter;
        flatten[counter++] = v[node] * -1;
    }

    private static void dfsL(List<List<Integer>> g, int node, int[] v) {
        lIn[node] = counter;
        lFlatten[counter++] = v[node];

        for (int i = 0; i < g.get(node).size(); ++i) {
            dfsL(g, g.get(node).get(i), v);
        }

        lOut[node] = counter;
        lFlatten[counter++] = v[node] * -1;
    }


    private static void preprocess(int pos, int[][] pre, List<List<Integer>> tree, int[] traverse, int depth, int last, int[] tin, int[] tout) {
        tin[pos] = counter++;
        traverse[depth] = pos;

        for (int i = 0; depth - (1 << i) >= 0; ++i) {
            pre[pos][i] = traverse[depth - (1 << i)];
        }

        for (int i = 0; i < tree.get(pos).size(); ++i) {
            if (tree.get(pos).get(i) != last)
                preprocess(tree.get(pos).get(i), pre, tree, traverse, depth + 1, pos, tin, tout);
        }
        tout[pos] = counter++;
    }

    static int gcd(int a, int b) {

        while (b != 0) {
            int t = a;
            a = b;
            b = t % b;
        }
        return a;
    }


    static boolean submit = true;

    static void debug(String s) {
        if (!submit)
            System.out.println(s);
    }

    static void debug(int s) {
        if (!submit)
            System.out.println(s);
    }


    class Solution {
        public class Pair {
            public int start, end, c;

            public Pair(int start, int end, int c) {
                this.start = start;
                this.end = end;
                this.c = c;
            }
        }
        public List<String> maxNumOfSubstrings(String s) {
            int n = s.length();
            List<String> answer = new ArrayList<>();
            Map<Integer, Integer> f = new HashMap<>();
            Map<Integer, Integer> l = new HashMap<>();


            for (int i = 0; i < n; ++i) {
                if (!f.containsKey(s.charAt(i) - 'a')) {
                    f.put(s.charAt(i) - 'a', i);
                }
            }

            for (int i = n-1; i >= 0; --i) {
                if (!l.containsKey(s.charAt(i) - 'a')) {
                    l.put(s.charAt(i) - 'a', i);
                }
            }

            List<Pair> p = new ArrayList<>();
            for (int i = 0; i < 26; ++i) {
                int start = f.getOrDefault(i, -1);
                int end = l.getOrDefault(i, -1);
                if (start != -1) {
                    for (int j = start; j < end; ++j) {
                        end = Math.max(end, l.get(s.charAt(j) - 'a'));
                        if (start > f.get(s.charAt(j) - 'a')) {
                            start = Math.min(start, f.get(s.charAt(j) - 'a'));
                            j = start;
                        }

                    }
                    p.add(new Pair(start, end, i));
                }
            }

            p.sort(Comparator.comparingInt(a -> a.end));
            int lastEnd = 0;
            for (Pair pair : p) {
                if (pair.start >= lastEnd) {
                    answer.add(s.substring(pair.start, pair.end + 1));
                    lastEnd = pair.end;
                }
            }

            return answer;
        }

    }


}