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.util.*;
import java.io.*;
public class a{
	static void flip(char [] a,int l,int r){
		for(int i=l;i<=r;i++){
		   if(a[i]=='0')a[i]='1';
		   else a[i]='0';
		}
		while(l<=r){
			char temp=a[l];
			a[l]=a[r];
			a[r]=temp;
			l++;r--;
		}
	}

    public static void main(final String [] args) throws IOException{
	   BufferInput sc=new BufferInput();
	   int t=sc.nextInt();
	   while(t-->0){
		   int n=sc.nextInt();
		   char [] a=sc.next().toCharArray();
		   char [] b=sc.next().toCharArray();
		   boolean equal=true;
		   for(int i=0;i<n;i++){
			   if(a[i]!=b[i]){equal=false;break;}
		   }
		   if(equal){
			   System.out.println("0");
			   continue;
		   }





		   List<Integer> list=new ArrayList<>();

		   for(int i=n-1;i>=0;i--){
			   if(a[i]==b[i])continue;

			   if(b[i]!=a[0]){
				   list.add(i+1);
				   flip(a,0,i);
			   }
			   else{
				   for(int j=i;j>=0;j--){
					   if(a[j]==b[i]){
						   list.add(j+1);
						   flip(a,0,j);
						   list.add(i+1);
						   flip(a,0,i);
						   break;
					   }
				   }
			   }
		   }

		   StringBuilder sb=new StringBuilder("");
		   sb.append(list.size()+" ");
		   for(int x : list)sb.append(x+" ");
		   System.out.println(sb.toString());

	   }
	   
	}
}


























































































  
 
 
class BufferInput 
 
{	
	final private int BUFFER_SIZE = 1 << 16;
	
	private DataInputStream din;
	
	private byte[] buffer;
	
	private int bufferPointer, bytesRead;
	
	public BufferInput() {
		din = new DataInputStream(System.in);
		buffer = new byte[BUFFER_SIZE];
		bufferPointer = bytesRead = 0;
	}
 
	public BufferInput(String file_name) throws IOException {
		din = new DataInputStream(new FileInputStream(file_name));
		buffer = new byte[BUFFER_SIZE];
		bufferPointer = bytesRead = 0;
    }
    
	public String readLine() throws IOException {
		byte[] buf = new byte[64];
		int cnt = 0, c;
		while ((c = read()) != -1) {
			if (c == '\n')
				break;
			buf[cnt++] = (byte) c;
		}
		return new String(buf, 0, cnt);
	}
    
    public String next() throws IOException{
 
		byte c = read();
		while(Character.isWhitespace(c)){
			c = read();
		}
		
		StringBuilder builder = new StringBuilder();
		builder.append((char)c);
		c = read();
		while(!Character.isWhitespace(c)){
			builder.append((char)c);
			c = read();
		}
		
		return builder.toString();
	}
 
	public int nextInt() throws IOException {
		int ret = 0;
		byte c = read();
		while (c <= ' ')
			c = read();
		boolean neg = (c == '-');
		if (neg)
			c = read();
		do {
			ret = ret * 10 + c - '0';
		} while ((c = read()) >= '0' && c <= '9');
 
		if (neg)
			return -ret;
		return ret;
	}
	
	public int[] nextIntArray(int n) throws IOException {
		int arr[] = new int[n];
		for(int i = 0; i < n; i++){
			arr[i] = nextInt();
		}
		return arr;
	}
 
	public long nextLong() throws IOException {
		long ret = 0;
		byte c = read();
		while (c <= ' ')
			c = read();
		boolean neg = (c == '-');
		if (neg)
			c = read();
		do {
			ret = ret * 10 + c - '0';
		} while ((c = read()) >= '0' && c <= '9');
		if (neg)
			return -ret;
		return ret;
	}
	
	public long[] nextLongArray(int n) throws IOException {
		long arr[] = new long[n];
		for(int i = 0; i < n; i++){
			arr[i] = nextLong();
		}
		return arr;
	}
 
	public char nextChar() throws IOException{
		byte c = read();
		while(Character.isWhitespace(c)){
			c = read();
		}
		return (char) c;	
	}
	
	public double nextDouble() throws IOException {
		double ret = 0, div = 1;
		byte c = read();
		while (c <= ' ')
			c = read();
		boolean neg = (c == '-');
		if (neg)
			c = read();
 
		do {
			ret = ret * 10 + c - '0';
		} while ((c = read()) >= '0' && c <= '9');
 
		if (c == '.') {
			while ((c = read()) >= '0' && c <= '9') {
				ret += (c - '0') / (div *= 10);
			}
		}
 
		if (neg)
			return -ret;
		return ret;
    }
    
	public double[] nextDoubleArray(int n) throws IOException {
		double arr[] = new double[n];
		for(int i = 0; i < n; i++){
			arr[i] = nextDouble();
		}
		return arr;
	}
 
	private void fillBuffer() throws IOException {
		bytesRead = din.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 (din == null)
			return;
		din.close();
	}
 
}