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.DataInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;

public class C {
	private static Reader reader = new Reader();
	private static PrintWriter writer = new PrintWriter(System.out);

	public static void main(String[] args) throws IOException {
		int t = reader.readInt();
		while (t-- > 0) {
			int n = reader.readInt();
			char[] a = reader.readString().toCharArray();
			char[] b = reader.readString().toCharArray();
			ArrayList<Integer> ans = new ArrayList<>();
			int l = 0; 
			int r = n - 1;
			boolean reverse = false;
			int id = n - 1;
			while (id >= 0) {
				if (reverse) {
					if (flip(a[l]) == b[id]) {
						l++;
						id--;
						continue;
					}
					if (flip(a[l]) != flip(a[r])) {
						ans.add(1);
					}
					ans.add(id + 1);
					reverse = false;
					r--;
				} else {
					if (a[r] == b[id]) {
						r--;
						id--;
						continue;
					}
					if (a[l] != a[r]) {
						ans.add(1);
					}
					ans.add(id + 1);
					reverse = true;
					l++;
				}
				id--;
			}
			writer.print(ans.size() + " ");
			for (Integer xInteger : ans) {
				writer.print(xInteger + " ");
			}
			writer.println();
		}
		reader.close();
		writer.close();
	}
	
	static char flip(char x) {
		if (x == '0') {
			return '1';
		}
		return '0';
	}
	
	static ArrayList<Integer> brute(char[] a, char[] b, int n) {
		ArrayList<Integer> ans = new ArrayList<>();
		for (int i = n - 1; i >= 0; i--) {
			if (a[i] == b[i]) {
				continue;
			}
			if (a[0] != a[i]) {
				ans.add(1);
				a[0] = flip(a[0]);
			}
			ans.add(i + 1);
			int l = 0, r = i;
			while (l <= r) {
				if (l == r) {
					a[l] = flip(a[l]);
					break;
				}
				char ll = flip(a[r]);
				char rr = flip(a[l]);
				a[l] = ll;
				a[r] = rr;
				l++;
				r--;
			}	
		}
		return ans;
	}

	static class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream input;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public Reader() {
			this(System.in);
		}

		public Reader(String fileName) throws FileNotFoundException {
			this(new FileInputStream(fileName));
		}

		public Reader(InputStream inputStream) {
			input = new DataInputStream(inputStream);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readString() throws IOException {
			byte c = read();
			while (c <= ' ') {
				c = read();
			}
			StringBuilder string = new StringBuilder();
			do {
				if (Character.isValidCodePoint(c)) {
					string.appendCodePoint(c);
				}
				c = read();
			} while (!isWhitespace(c));
			return string.toString();
		}

		public int readInt() throws IOException {
			int result = 0;
			byte c = read();
			while (c <= ' ') {
				c = read();
			}
			boolean isNegative = (c == '-');
			if (isNegative) {
				c = read();
			}
			do {
				result = result * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (isNegative) {
				return -result;
			}
			return result;
		}

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

		public long readLong() throws IOException {
			long result = 0;
			byte c = read();
			while (c <= ' ') {
				c = read();
			}
			boolean isNegative = (c == '-');
			if (isNegative) {
				c = read();
			}
			do {
				result = result * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (isNegative) {
				return -result;
			}
			return result;
		}

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

		public double readDouble() throws IOException {
			double result = 0, div = 1;
			byte c = read();
			while (c <= ' ') {
				c = read();
			}
			boolean isNegative = (c == '-');
			if (isNegative) {
				c = read();
			}
			do {
				result = result * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

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

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

		private void fillBuffer() throws IOException {
			bytesRead = input.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 (input == null) {
				return;
			}
			input.close();
		}

	}
}