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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;
//import com.google.common.collect.HashMultiset; 
//import com.google.common.collect.Multiset;



public class code6 {

	static int ans = 0;
	static int[] arr;
	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

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

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

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

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
		public int[] nextIntArray(int n) {
	    	int[] a = new int[n];
	    	for(int i = 0; i < n; i ++)
	    		a[i] = nextInt();
	    	return a;
	    }
	    
	    public long[] nextLongArray(int n) {
	    	long[] a = new long[n];
	    	for(int i = 0; i < n; i ++)
	    		a[i] = nextLong();
	    	return a;
	    }
	    
	    public double[] nextDoubleArray(int n) {
	    	double[] a = new double[n];
	    	for(int i = 0; i < n; i ++)
	    		a[i] = nextDouble();
	    	return a;
	    }
	}
	public static void main(String[] args) throws CloneNotSupportedException {
		// TODO Auto-generated method stub
		FastReader scn = new FastReader();
		PrintWriter out = new PrintWriter(System.out);
		int t = scn.nextInt();
		//int p = t;
		while(t-->0) {
			int n = scn.nextInt();
			char[] s1 = scn.next().toCharArray();
			char[] s2 = scn.next().toCharArray();
			int[] a = new int[n];
			int[] b = new int[n];
			for(int i=0; i<n; i++)
				a[i] = Integer.parseInt(String.valueOf(s1[i]));
			for(int i=0; i<n; i++)
				b[i] = Integer.parseInt(String.valueOf(s2[i]));
			
			ArrayList<Integer> list = new ArrayList<Integer>();
			int l = 0, cnt = n - 1;
	        boolean flag = false;
			for(int i=n-1;i>=0; i--)
	        {
	            if (!flag)
	            {
	                if (a[cnt] != b[i])
	                {
	                    if (a[l] == b[i]) list.add(1);
	                    list.add(i + 1);l++;flag = true;
	                }
	                else cnt--;
	                
	            }
	            else if(flag)
	            {
	                
	                if (a[l] == b[i])
	                {
	                    if (a[cnt] != b[i]) list.add(1);
	                    list.add(i + 1);cnt--;flag = false;
	                }
	                else l++;
	                
	            }
	        }
//			int p = a[0];
//			if(k!=n) {
//				int l = Math.abs(k/2 - 0);
//				if(k%2 == 1) {
//					if(0<=k/2)
//						p = a[k/2+l+1];
//					else
//						p = a[k/2-l+1];
//				}else {
//					if(0<k/2)
//						p = a[k/2+l];
//					else
//						p=a[k/2-l];
//				}
//				if((c)%2 == 1)
//					p^=1;
//			}
//			if(p != b[0])
//				list.add(1);
			
			out.print(list.size() + " ");
			
			for(Integer i: list)
				out.print(i + " ");
			out.println();
		}
		out.flush();
	}
	
	
public static void topologicalSortUtil( int v, boolean visited[], Stack<Integer> stack, ArrayList<Integer>[] graph)  
			    {  
			        // Mark the current node as visited.  
			        visited[v] = true;  
			        Integer i;  
			    
			        // Recur for all the vertices adjacent  
			        // to thisvertex  
			        Iterator<Integer> it = graph[v].iterator();  
			        while (it.hasNext())  
			        {  
			            i = it.next();  
			            if (!visited[i])  
			                topologicalSortUtil(i, visited, stack, graph);  
			        }  
			    
			      
			        stack.push(new Integer(v));  
			    }  
			    
			    
public static int[] topologicalSort(int V, ArrayList<Integer>[] graph)  
			    {  
			        Stack<Integer> stack = new Stack<Integer>();  
			    
			      
			        boolean visited[] = new boolean[V];  
			        for (int i = 0; i < V; i++)  
			            visited[i] = false;  
			     
			        for (int i = 0; i < V; i++)  
			            if (visited[i] == false)  
			                topologicalSortUtil(i, visited, stack, graph);  
			     
			        int[] arr = new int[V];
			        int i = 0;
			        Arrays.fill(arr, -1);
			        while (stack.empty()==false) {
			        	arr[stack.pop()] = i;
			        	i++;
			        }
			        return arr;
			    }  
	public static int rec(String str, char a) {
		if(str.length() == 1) {
			if(str.charAt(0) == a)
				return 0;
			else
				return 1;
		}
		int n = str.length()/2;
		int c = 0;
		for(int i=0; i<n; i++) {
			if(str.charAt(i) != a)
				c++;
		}
		int ans1 = c+rec(str.substring(n), (char)(a+1));
		c = 0;
		for(int i=n; i<2*n; i++) {
			if(str.charAt(i) != a)
				c++;
		}
		int ans2 = c + rec(str.substring(0,n), (char)(a+1));
		return Math.min(ans1, ans2);
		
	}
	
	public static class stud{
		private int roll;
		String name;
	}
	
	public static void dfs(ArrayList<Integer>[] tree, int i, int l, int[] level) {
		level[i] = l;
		for(int j=0; j<tree[i].size(); j++) {
			dfs(tree, tree[i].get(j), l+1, level);
		}
	}
	public static void dfs(int i, boolean[] vis, int[] parent, int[] level, int a, int last) {
		if(i == -1)
			return;
		if(level[last]-level[i] == a) {
			if(!vis[i])
				ans++;
			vis[i] = true;
			last = i;
		}
		dfs(parent[i], vis, parent, level, a, last);
	}
	public static int[] PossibleKey(int[] arr) {
		int[] ans = new int[4];
		for(int i=0; i<4; i++)
			arr[i] = 1;
		int[] help = new int[4];
		int i = 0;
		int ch = 0;
		int cl = 0;
		for(i = 1; i<4; i++) {
			if(arr[i]>arr[i-1]) {
				for(int j=0; j<4; j++)
					help[j]++;
			}
			if(arr[i]<arr[i-1]) {
				for(int j=0; j<4; j++)
					help[j]--;
			}
			for(int j=0; j<4; j++) {
				if(help[j]+j<0 || help[j]+j>4)
					ans[j] = 0;
			}
		}
		return ans;
		
	}
	
//	public static int dfs(ArrayList<Integer>[] graph, boolean[] vis, int i) {
//		int s= 1;
//		vis[i] = true;
//		for(int j=0; j<graph[i].size(); j++) {
//			if(!vis[graph[i].get(j)])
//				s += dfs(graph, vis, graph[i].get(j));
//		}
//		if(s%2 == 0)
//			ans++;
//		return s;
//	}
	
  
	public static boolean check(int mid, int c, int[] arr, int k) {
		int ans = 0;
		for(int i=0; i<arr.length; i++) {
			if(c==0) {
				ans++;
				c = (c+1)%2;
			}else {
				if(arr[i]<=mid) {
					ans++;
					c = (c+1)%2;
				}
			}
		}
		return ans>=k;
	}
	public static long power(long x, long y, int p) 
    { 
       
        long res = 1;      
         
        x = x % p;  
  
       if (x == 0) return 0;     
  
        while (y > 0) 
        { 
            
            if((y & 1)==1) 
                res = (res * x) % p; 
 
            y = y >> 1;  
            x = (x * x) % p;  
        } 
        return res; 
    } 
	
	public static int[] nextG(int[] arr, int n) {
		int[] ans = new int[n];
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(0);
		for(int i=1; i<n; i++) {
			while(!stack.isEmpty() && arr[stack.peek()]<=arr[i])
				ans[stack.pop()] = i;
			stack.push(i);
		}
		while(!stack.isEmpty())
			ans[stack.pop()] = n;
		return ans;
	}
	public static int[] nextGRev(int[] arr, int n) {
		int[] ans = new int[n];
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(n-1);
		for(int i=n-2; i>=0; i--) {
			while(!stack.isEmpty() && arr[stack.peek()]<=arr[i])
				ans[stack.pop()] = i;
			stack.push(i);
		}
		while(!stack.isEmpty())
			ans[stack.pop()] = -1;
		return ans;
	}
	
	static int largestPower(int n, int p) { 
       
        int x = 0; 
 
        while (n > 0) { 
            n /= p; 
            x += n; 
        } 
        return x; 
    } 
  

    static int power(int x, int y, int p) { 
        int res = 1;  
        x = x % p;  
      
        while (y > 0) { 
            
            if (y % 2 == 1) { 
                res = (res * x) % p; 
            } 
  
             
            y = y >> 1;
            x = (x * x) % p; 
        } 
        return res; 
    }
	
	static int Fact(int n, int p) { 
        if (n >= p) { 
            return 0; 
        } 
  
        int res = 1; 
 
        boolean isPrime[] = new boolean[n + 1]; 
        Arrays.fill(isPrime, true); 
        for (int i = 2; i * i <= n; i++) { 
            if (isPrime[i]) { 
                for (int j = 2 * i; j <= n; j += i) { 
                    isPrime[j] = false; 
                } 
            } 
        } 

        for (int i = 2; i <= n; i++) { 
            if (isPrime[i]) { 

                int k = largestPower(n, i); 
  
        
                res = (int) ((res * power((long)i, (long)k, p)) % p); 
            } 
        } 
        return res; 
    } 
	
	public static class Pair implements Comparable<Pair>{
		int i;
		int n;
		Pair(int x, int z){
			i = x;
			n = z;
		}
		public int compareTo(Pair p) {
			return this.n-p.n;
		}

	}
	public static boolean isCyclicUtil(int i, boolean[] visited, 
            boolean[] recStack, ArrayList<Integer>[] graph)  
{ 

// Mark the current node as visited and 
// part of recursion stack 
if (recStack[i]) 
	return true; 

if (visited[i]) 
	return false; 

visited[i] = true; 

recStack[i] = true; 
List<Integer> children = graph[i]; 

for (Integer c: children) 
	if (isCyclicUtil(c, visited, recStack, graph)) 
		return true; 

recStack[i] = false; 

return false; 
} 


public static boolean isCyclic(int V, ArrayList<Integer>[] graph)  
{ 


boolean[] visited = new boolean[V]; 
boolean[] recStack = new boolean[V]; 

for (int i = 0; i < V; i++) 
	if (isCyclicUtil(i, visited, recStack, graph)) 
		return true; 

return false; 
} 
    
}