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 D {
	public static void main (String[] args) { new D(); }

	public D() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("");

		int T = fs.nextInt();
		while(T-->0) {
			int n = fs.nextInt();
			char[] a = fs.next().toCharArray();
			char[] b = fs.next().toCharArray();
			
			if(n == 1) {
				if(a[0] != b[0]) {
					out.println("1 1");
				}
				else {
					out.println(0);
				}
				continue;
			}
			
			ArrayList<Integer> res = new ArrayList<>();
			for(int i = 0; i < n; i += 2) {
				if(i == n-1) {
					if(a[i] != b[i])
						flipBit(res, i);
					continue;
				}
				if(a[i] != b[i] && a[i+1] != b[i+1]) {
					if(a[i] != a[i+1]) {
						res.add(i);
						res.add(i+1);
						res.add(i);
						if(i > 0) res.add(i-1);
					}
					else {
						res.add(i+1);
						res.add(1);
						res.add(i+1);
					}
				}
				else if(a[i] != b[i]) flipBit(res, i);
				else if(a[i+1] != b[i+1]) flipBit(res, i+1);
			}
			if(res.size() > 2*n) throw null;
			out.print(res.size());
			for(int x : res) out.print(" " + (x + 1));
			out.println();
			
//			for(int x : res) {
//				a = doOp(a, x);
//			}
//			String A = new String(a);
//			String B = new String(b);
//			if(!A.equals(B)) {
//				System.out.println("BAD");
//			}
			
			
		}
		
		out.close();
	}

	void flipBit(ArrayList<Integer> res, int i) {
		res.add(i);
		res.add(0);
		res.add(i);
	}
	
	char[] doOp(char[] a, int idx) {
		char[] b = a.clone();
		for(int i = 0, j = idx; j >= 0; j--, i++) {
			char flip = (char)(((a[j]-'0')^1)+'0');
//			System.out.println("   " + i + " " + j + " :: " + a[j] + " " + flip);
			b[i] = flip;
		}
		return b;
	}

	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			}
			catch (Exception e) {
				in = new BufferedInputStream(System.in, BS);
			}
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}