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.*;
import java.math.*;
import java.math.BigInteger; 
//import javafx.util.*; 
public final class B
{    
    static StringBuilder ans=new StringBuilder();
    static FastReader in=new FastReader();
    static ArrayList<ArrayList<Integer>> g;
    static long mod=1000000007;
   // static boolean set[];   

    public static void main(String args[])throws IOException
    {  
     int T=i();
     while(T-->0)
     {
    	int N=i();
    	 String X=in.next();
    	String Y=in.next();
    	String X1=reverse(X);
    	int st1=0,st2=0,end1=N-1,end2=N-1;
    	boolean f=true; int x=0;
    	for(int i=N-1; i>=0; i--)
    	{
           if(f)
           {
    		if(Y.charAt(i)==X.charAt(end1))
    		{
    			end1--;
    		}
    		else
    		{
    			f=false;
    			if(i==0)
    			{
    				x++;
    				ans.append(1+" ");
    			}
    			else
    			{
    				
    				if(X1.charAt(end2)==Y.charAt(i))
    				{
    					x++; ans.append((i+1)+" ");
    				}
    				else
    				{   		
    					x+=2;
    					ans.append(1+" ");
    					ans.append((i+1)+" ");
    				}
    				end2--;
    			}
    		}
           }
           else
           {
        	   if(Y.charAt(i)==X1.charAt(end2))
        	   {
        		   end2--;
        		   
        	   }
        	   else
        	   {
        		   f=true;
        		   if(i==0)
       			    {
       				ans.append(1+" "); x++;
       			     }
       			       else
       			       {
       				
       				 if(X.charAt(end1)==Y.charAt(i))
       				    {
       					 x++;
       					ans.append((i+1)+" ");
       				      }
       				 else
       				   {   			
       					 x+=2;
       					ans.append(1+" ");
       					ans.append((i+1)+" ");
       				     }
       				end1--;
       			}
        	   }
           }
    	}
    	
    	
    	System.out.println(x+" "+ans);
    	ans.delete(0, ans.length());
    }
  }
   	
    	static String reverse(String X)
    	{
    		StringBuilder st=new StringBuilder();
    		int N=X.length();
    		for(int i=N-1; i>=0; i--)
    		{
    			int a=X.charAt(i)-'0';
    			a=(a+1)%2;
    			st.append(a+"");
    		}
    		return st.toString();
    	}
    static int f1(int A[][],int i,int num,int N)
    {
    	for(int j=0; j<N; j++)   	
    	{
    		if(A[i][j]==num)return j;
    	}
    	return -1;
    }
    
    static int f2(int A[][],int j,int num,int N)
    {
    	for(int i=0; i<N; i++)   	
    	{
    		if(A[i][j]==num)return i;
    	}
    	return -1;
    }
   
    
   
    
    static long lower_Bound(long A[],int low,int high, long x) 
    { 
        if (low > high) 
        if (x >= A[high]) 
            return A[high]; 
  
        int mid = (low + high) / 2; 
         
        if (A[mid] == x) 
            return A[mid]; 
  
        if (mid > 0 && A[mid - 1] <= x && x < A[mid]) 
            return A[mid - 1]; 

        if (x < A[mid]) 
            return lower_Bound( A, low, mid - 1, x); 

        return lower_Bound(A, mid + 1, high, x); 
    } 
    


    static void sort(long[] a) //check for long
    {
        ArrayList<Long> l=new ArrayList<>();
        for (long i:a) l.add(i);
        Collections.sort(l);
        for (int i=0; i<a.length; i++) a[i]=l.get(i);
    }

    static String swap(String X,int i,int j)
    {
        char ch[]=X.toCharArray();
        char a=ch[i];
        ch[i]=ch[j];
        ch[j]=a;
        return new String(ch);
    }

    static int sD(long n)  
    {  

        if (n % 2 == 0 )  
            return 2;  

        for (int i = 3; i * i <= n; i += 2) {  
            if (n % i == 0 )  
                return i;  
        }  

        return (int)n;  
    }  

    static void setGraph(int N)
    {
       // set=new boolean[N+1];
        g=new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<=N; i++)
            g.add(new ArrayList<Integer>());
    }

    static void DFS(int N,int d)
    {
      //  set[N]=true;
        d++;
        for(int i=0; i<g.get(N).size(); i++)
        {
            int c=g.get(N).get(i);
            
        }
    }

    static  long pow(long a,long b)
    {
        long mod=1000000007;
        long pow=1;
        long x=a;
        while(b!=0)
        {
            if((b&1)!=0)pow=(pow*x)%mod;
            x=(x*x)%mod;
            b/=2;
        }
        return pow;
    }

    static long toggleBits(long x)//one's complement || Toggle bits
    {
        int n=(int)(Math.floor(Math.log(x)/Math.log(2)))+1;

        return ((1<<n)-1)^x;
    }

    static int countBits(long a)
    {
        return (int)(Math.log(a)/Math.log(2)+1);
    }

    static long fact(long N)
    { 
        long n=2; 
        if(N<=1)return 1;
        else
        {
            for(int i=3; i<=N; i++)n=(n*i)%mod;
        }
        return n;
    }

    static int kadane(int A[])
    {
        int lsum=A[0],gsum=A[0];
        for(int i=1; i<A.length; i++)
        {
            lsum=Math.max(lsum+A[i],A[i]);
            gsum=Math.max(gsum,lsum);
        }
        return gsum;
    }

    static void sort(int[] a) {
        ArrayList<Integer> l=new ArrayList<>();
        for (int i:a) l.add(i);
        Collections.sort(l);
        for (int i=0; i<a.length; i++) a[i]=l.get(i);
    }

    static boolean isPrime(long N)
    {
        if (N<=1)  return false; 
        if (N<=3)  return true; 
        if (N%2 == 0 || N%3 == 0) return false; 
        for (int i=5; i*i<=N; i=i+6) 
            if (N%i == 0 || N%(i+2) == 0) 
                return false; 
        return true; 
    }

    static int i()
    {
        return in.nextInt();
    }

    static long l()
    {
        return in.nextLong();
    }

    static int[] input(int N){
        int A[]=new int[N];
        for(int i=0; i<N; i++)
        {
            A[i]=in.nextInt();
        }
        return A;
    }

    static long[] inputLong(int N)     {
        long A[]=new long[N];
        for(int i=0; i<A.length; i++)A[i]=in.nextLong();
        return A;
    }

    static long GCD(long a,long b) 
    {
        if(b==0)
        {
            return a;
        }
        else return GCD(b,a%b );
    }

}
//Code For FastReader
//Code For FastReader
//Code For FastReader
//Code For FastReader
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;
    }

}