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.*;


public class Main {

    public static void main(String[] args) throws IOException {
//        int []moves = {11, 1, 10, 8, 7, 1, 6, 1, 4, 1, 2, 1};
//        int []moves = {7, 1, 10 ,8, 7 ,1 ,2, 1};
//        StringBuilder s = new StringBuilder("0110011011");
//        for (int i = 1; i < moves.length; i++){
//            if(moves[i] == 1){
//                if (s.charAt(0) == '0')
//                    s.setCharAt(0, '1');
//                else
//                    s.setCharAt(0, '0');
//            }else {
//                moves[i]--;
//                for (int j = 0; j <= moves[i]; j++) {
//                    if (s.charAt(j) == '0') {
//                        s.setCharAt(j, '1');
//                    } else {
//                        s.setCharAt(j, '0');
//                    }
//                }
//                StringBuilder pre = new StringBuilder(s.substring(0, moves[i]));
//                s.replace(0, moves[i], pre.reverse().toString());
//            }
//        }
//        System.out.println(s.toString());
        int testCases = GetInput.getInt();
        while (testCases-- > 0) {
            int n = GetInput.getInt();
            StringBuilder a = GetInput.getInputString();
            String b = GetInput.getInputString().toString();
            int i = n - 1;
            ArrayList<Integer> steps = new ArrayList<>();
            while (i > -1) {
                if (a.charAt(i) == b.charAt(i)) {
                    i--;
                    continue;
                }
                if (a.charAt(0) != a.charAt(i)) {
                    //change first char
                    steps.add(0);
                    if (a.charAt(0) == '0')
                        a.setCharAt(0, '1');
                    else
                        a.setCharAt(0, '0');
                } else {
                    //change all characters uptil i
                    steps.add(i);
                    for (int j = 0; j <= i; j++) {
                        if (a.charAt(j) == '0') {
                            a.setCharAt(j, '1');
                        } else {
                            a.setCharAt(j, '0');
                        }
                    }
                    StringBuilder reverse = new StringBuilder(a.substring(0, i+1));
                    a.replace(0, i, reverse.reverse().toString());
                    i--;
                }
            }
            System.out.print(steps.size()+ " ");
            for (int j = 0; j<steps.size(); j++){
                System.out.print((steps.get(j)+1)+" ");
            }
            System.out.println();
        }
    }

    static int rec(String s, char ch) {
        if (s.length() == 1) {
            if (ch == s.charAt(0)) {
                return 0;
            }
            return 1;
        }
        int cost1 = 0, cost2 = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (ch != s.charAt(i) && i < s.length() / 2) {
                cost1++;
            }
            if (ch != s.charAt(i) && i >= s.length() / 2) {
                cost2++;
            }
        }
        return (int) min(cost1 + rec(s.substring(s.length() / 2), (char) (ch + 1)), cost2 + rec(s.substring(0, s.length() / 2), (char) (ch + 1)));

    }

    static long fff(long key, long freq, long k) {
        return key + 1 + (freq - 1) * (k);
    }

    static int rec(int sum, int n) {
        if (n == 0) {
            return sum;
        }
        return rec(n % 10 + sum, n / 10);
    }

    static int foo(int n, int r) {
        if (n > 0) return (n % r + foo(n / r, r));
        else return 0;
    }

    private static long mod(long b) {
        if (b < 0) {
            return -b;
        }
        return b;
    }

    private static int findEnd(int i, int n, int b) {
        if ((i / b) + b > n - 1) {
            return n - 1;
        }
        return (i / b) + b - 1;
    }

    static int KnapSack(int val[], int wt[],
                        int n, int W) {
        // matrix to store final result
        int dp[][] = new int[2][W + 1];

        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= W; w++) {
                if (wt[i - 1] <= w)
                    dp[i % 2][w] = Math.max(dp[(i - 1) % 2][w], val[i - 1] + dp[(i - 1) % 2][w - wt[i - 1]]);
                else
                    dp[i % 2][w] = dp[(i - 1) % 2][w];
            }
        }

        return dp[n % 2][W];
    }

    //        String []arr = {"USA", "United States", "Washington", "California", "New York", "Los Angeles", "Florida", "Texas",
//                "Chicago", "Boston", "San Francisco", "Seattle", "Brooklyn", "San Diego" , "Michigan", "Colorado", "Austin", "Pennsylvania", "Philadelphia", "Ohio", "New Jersey", "Carolina"};
//        String []arr = {"Australia", "Sydney", "Melbourne", "Canberra"};
//        String []arr = {"Canada", "Ontario", "Ottawa", "Richmond", "Vancouver", "Alberta", "Toronto", "Victoria"};
//        String []arr = {"Australia", "Sydney", "Melbourne", "Canberra"};
//        String []arr = {"England", "London", "UK", "Britain", "Manchester"};
//        String []arr = {"India", "Delhi", "Bangalore", "Mumbai", "Chennai", "Pune", "Noida", "Gurgaon", "Kolkata"};
//        String []arr = {"New Zealand", "Auckland"};
////        String []arr = {"France", "Paris"};
//        File file = new File("/Users/jacksonjose/Downloads/HTTPclient-server-master/PractiseCompetitive/src/2018.csv");
//        processor(arr, file);
//        file = new File("/Users/jacksonjose/Downloads/HTTPclient-server-master/PractiseCompetitive/src/2019.csv");
//        processor(arr, file);
//    }
//
//    private static void processor(String []arr, File file) throws IOException {
//        Count c = grouper(arr, new Count(0,0,0), file);
//        System.out.println(arr[0]);
//        System.out.println("Total Count, " + (c.pos+c.neg));
//        System.out.println("-1, " + c.neg);
//        System.out.println("1, " + c.pos);

    private static int numerOftwos(int n) {
        int ans = 0;
        while (n % 2 == 0) {
            n /= 2;
            ans++;
        }
        return ans;
    }

    public static int oddPrimeFactors(int n) {
        while (n % 2 == 0) {
            n /= 2;
        }
        int ans = 0;

        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            while (n % i == 0) {
                n /= i;
                ans++;
            }
        }

        if (n > 2)
            ans++;
        return ans;
    }

    private static boolean onlyPowerOf2(int n) {
        if (n == 2) {
            return false;
        }
        while (n > 1) {
            if (n % 2 == 0) {
                n /= 2;
            } else {
                return false;
            }
        }
        return true;
    }

//    private static Count grouper(String []key, Count c, File file) throws IOException {
//        BufferedReader br = new BufferedReader(new FileReader(file));
//
//        String st;
//        st = br.readLine();
//        int i = 0;
//        while (st!=null){
//            String []strings = st.split(",(?=(?:[^\"]*\"[^\"]*\")*[^\"]*$)", -1);
//            if (isKeyContained(strings[0], key)){
//                st = br.readLine();
//                strings = st.split(",");
//                if (isNumeric(strings[0])){
//                    int num = Integer.parseInt(strings[0]);
//                    if (num == -1){
//                        c.neg += Integer.parseInt(strings[1]);
//                    }
//                    else {
//                        c.pos += Integer.parseInt(strings[1]);
//                    }
//                }
//                else {
//                    continue;
//                }
//                st = br.readLine();
//                strings = st.split(",");
//                if (isNumeric(strings[0])){
//                    int num = Integer.parseInt(strings[0]);
//                    if (num == -1){
//                        c.neg += Integer.parseInt(strings[1]);
//                    }
//                    else {
//                        c.pos += Integer.parseInt(strings[1]);
//                    }
//                }
//            }
//            st = br.readLine();
//        }
//        return c;
//    }

//    private static boolean isKeyContained(String string, String[] key) {
//        for (String str : key){
//            if (string.contains(str)){
//                return true;
//            }
//        }
//        return false;
//    }

//    private static boolean isNumeric(String str) {
//        return str.matches("-?\\d+(\\.\\d+)?");
//    }


    private static boolean isMultiple(double i, double x) {
        if (x % i == 0) {
            return false;
        }
        return true;
    }

    private static int ff(long num) {
        return (int) (num % (1000000007));
    }

    private static boolean notOverlap(long[] t1, long[] t2) {
        return t1[0] >= t2[1];
    }


    private static long max(long in, long in1) {
        if (in > in1) {
            return in;
        }
        return in1;
    }

    private static long min(long in, long in1) {
        if (in > in1) {
            return in1;
        }
        return in;
    }

}


class GetInput {
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

    static char[] getCharArray() {
        char[] charArray;
        try {
            StringBuilder string = getInputString();
            charArray = new char[string.length()];
            for (int i = 0; i < string.length(); i++) {
                charArray[i] = string.charAt(i);
            }
            return charArray;
        } catch (Exception e) {
            e.printStackTrace();
        }
        charArray = new char[0];
        return charArray;
    }

    static int[] getArrayInt() {
        String[] string;
        int[] array;
        try {
            string = bufferedReader.readLine().split("\\s+");
            array = new int[string.length];
            for (int i = 0; i < string.length; i++) {
                array[i] = Integer.parseInt(string[i]);
            }
            return array;
        } catch (IOException e) {
            e.printStackTrace();
        }

        int[] arra = new int[2];
        return arra;
    }

    static int getInt() {
        try {
            String string = bufferedReader.readLine();
            return Integer.parseInt(string);
        } catch (IOException e) {
            e.printStackTrace();
        }

        return 0;
    }

    static StringBuilder getInputString() {
        try {
            StringBuilder string = new StringBuilder();
            string.append(bufferedReader.readLine());
            return string;
        } catch (IOException e) {
            e.printStackTrace();
        }
        return new StringBuilder();
    }

    static long getLongInput() {
        try {
            String string = bufferedReader.readLine();
            return Long.parseLong(string);
        } catch (IOException e) {
            e.printStackTrace();
        }

        return 0;
    }

    static long[] getLongArrayInput() {
        String[] string;
        long[] array;
        try {
            string = bufferedReader.readLine().split("\\s+");
            array = new long[string.length];
            for (int i = 0; i < string.length; i++) {
                array[i] = Long.parseLong(string[i]);
            }
            return array;
        } catch (IOException e) {
            e.printStackTrace();
        }

        long[] arra = new long[2];
        return arra;
    }


    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));

            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
            return res * sgn;
        }

        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            }
            while (!isSpaceChar(c));

            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return readString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}

class HeapSort {
    void sort(long[] arr) {
        int n = arr.length;

        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        for (int i = n - 1; i > 0; i--) {
            long temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }

    private void heapify(long[] arr, int n, int i) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        if (l < n && arr[l] > arr[largest])
            largest = l;

        if (r < n && arr[r] > arr[largest])
            largest = r;

        if (largest != i) {
            long swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            heapify(arr, n, largest);
        }
    }
}