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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author sumit
 */
public class Main {
      public static void main(String[] args) {
            InputStream inputStream = System.in;
            OutputStream outputStream = System.out;
            InputReader in = new InputReader(inputStream);
            OutputWriter out = new OutputWriter(outputStream);
            C1PrefixFlipEasyVersion solver = new C1PrefixFlipEasyVersion();
            solver.solve(1, in, out);
            out.close();
      }

      static class C1PrefixFlipEasyVersion {
            public void solve(int testNumber, InputReader in, OutputWriter out) {
                  int t = in.nextInt();
                  while (t-- > 0) {
                        int n = in.nextInt();
                        String str1 = in.next();
                        String str2 = in.next();

                        Util uu = new Util(str1);
                        StringBuilder sb = new StringBuilder();
                        int count = 0;
                        for (int i = n - 1; i > 0; i--) {
                              if (uu.str.charAt(i) == str2.charAt(i)) {
                                    continue;
                              } else {
                                    if (uu.str.charAt(i) == uu.str.charAt(0)) {
                                          uu.doReverse(0, i);
                                          sb.append((i + 1));
                                          sb.append(" ");
                                          count++;
                                    } else {
                                          uu.doReverse(0, 0);
                                          sb.append("1 ");
                                          count++;
                                          uu.doReverse(0, i);
                                          ;
                                          sb.append((i + 1));
                                          sb.append(" ");
                                          count++;
                                    }
                              }
                        }

                        if (uu.str.charAt(0) != str2.charAt(0)) {
                              sb.append("1 ");
                              count++;
                        }

                        out.print(count + " ");
                        out.printLine(sb.toString());


                  }
            }

            class Util {
                  String str;

                  Util(String str) {
                        this.str = str;
                  }

                  void doReverse(int start, int end) {
                        StringBuilder sb = new StringBuilder();
                        for (int i = start; i <= end; i++) {
                              if (str.charAt(i) == '1') {
                                    sb.append("0");
                              } else {
                                    sb.append("1");
                              }
                        }
                        String ss = sb.reverse().toString();
                        sb = new StringBuilder();
                        sb.append(ss);
                        for (int i = end + 1; i < str.length(); i++) {
                              sb.append(str.charAt(i));
                        }

                        this.str = sb.toString();
                  }

            }

      }

      static class OutputWriter {
            private final PrintWriter writer;

            public OutputWriter(OutputStream outputStream) {
                  writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
            }

            public OutputWriter(Writer writer) {
                  this.writer = new PrintWriter(writer);
            }

            public void print(Object... objects) {
                  for (int i = 0; i < objects.length; i++) {
                        if (i != 0) {
                              writer.print(' ');
                        }
                        writer.print(objects[i]);
                  }
            }

            public void printLine(Object... objects) {
                  print(objects);
                  writer.println();
            }

            public void close() {
                  writer.close();
            }

      }

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

            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 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 & 15;

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

                  return res * sgn;
            }

            public String next() {
                  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) {
                  return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
            }

      }
}