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.ArrayList;
import java.util.InputMismatchException;
public class C658 {

	public static void main(String[] args) {
		FastScanner in = new FastScanner(System.in);
		int T = in.nextInt();
		StringBuilder sb = new StringBuilder();
		
		while(T --> 0) {
			int N = in.nextInt();
			
			String g = in.next();
			String h = in.next();
			
			int[] arr = new int[N];
			for(int i = 0; i < N; i++) {
				arr[i] = g.charAt(i) - '0';
			}
			
			int[] arr2 = new int[N];
			for(int i = 0; i < N; i++) {
				arr2[i] = h.charAt(i) - '0';
			}
			
			ArrayList<Integer> ans = new ArrayList<>();
			fill(N, arr, arr2, ans);
			
			//System.out.println("Ans = " + ans);
			sb.append(ans.size());
			sb.append(" ");
			for(int i = 0; i < ans.size(); i++) {
				sb.append(ans.get(i) + 1);
				if(i < ans.size() - 1) {
					sb.append(" ");
				}
				else {
					sb.append("\n");
				}
			}
		}
		
		System.out.print(sb);
	}
	
	public static void fill(int N, int[] arr, int[] arr2, ArrayList<Integer> list) {
		int pos = N-1;
		int[] temp = new int[N];
		while(pos >= 0) {
		//	System.out.println("pos = " + pos);
		//	System.out.println("arr = " + Arrays.toString(arr));
			if(arr[0] != arr2[pos]) {
				//System.out.println("opt1");
				list.add(pos);
				
				flip(arr, pos, temp);
				
				pos--;
			}
			else {
				//System.out.println("opt2");
				list.add(0);
				
				flip(arr, 0, temp);
				
				
			}
		}
	}
	
	public static void flip(int[] arr, int pos, int[] temp) {
		pos++;
		for(int i = 0; i < pos; i++) {
			temp[i] = 1 - arr[pos - 1 - i];
		}
		for(int i = 0; i <  pos; i++) {
			arr[i] = temp[i];
		}
	}
	
	/**
	 * Source: Matt Fontaine
	 */
	static class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int chars;

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

		int read() {
			if (chars == -1)
				throw new InputMismatchException();
			if (curChar >= chars) {
				curChar = 0;
				try {
					chars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (chars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

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

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

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		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 String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}

}
/*
5
2
01
10
5
01011
11100
2
01
01
10
0110011011
1000110100
1
0
1

outputCopy
3 1 2 1
6 5 2 5 3 1 2
0
9 4 1 2 10 4 1 2 1 5
1 1
*/