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.lang.*;
import java.io.*;
import java.util.Arrays;  
import java.math.BigInteger; 

public class Codechef
{
    static long modInverse(long a, long m) 
    { 
        long g = gcd(a, m); 
        if (g != 1) 
            System.out.println("Inverse doesn't exist"); 
        else 
        { 
            // If a and m are relatively prime, then modulo inverse 
            // is a^(m-2) mode m  
                                return (power(a, m - 2, m)); 
        } 
        return ((long)-1);
    } 
      
    // To compute x^y under modulo m 
    static long power(long x, long y, long m)  
    { 
        if (y == 0) 
            return 1; 
          
        long p = power(x, y / 2, m) % m; 
        p = (p * p) % m; 
      
        if (y % 2 == 0) 
            return p; 
        else
            return (x * p) % m; 
    } 
      
    // Function to return gcd of a and b 
    static long gcd(long a, long b)  
    { 
        if (a == 0) 
            return b; 
        return gcd(b % a, a); 
    }
    static boolean find(int N)
    {
        String r="";
        int rem=1%N;
        HashMap<Integer, Integer> h = new HashMap<Integer, Integer>();
        while ((rem!=0) && !h.containsKey(rem))
        {
            h.put(rem,r.length());
            rem=rem*10;
            r=r+(rem/N);
            rem=rem%N;
        }
        if (rem==0)
        return (false);
        else
        return (true);
    }
    static String sorts(String inputString) 
    { 
        // convert input string to char array 
        char tempArray[] = inputString.toCharArray(); 
          
        // sort tempArray 
        Arrays.sort(tempArray); 
          
        // return new sorted string 
        return new String(tempArray); 
    }
    static long qrt(double d)
    {
        long k=(long)(d);
        double x=-1+Math.sqrt(1+(8*d));
        x=x/2;
        long w=(long)(Math.ceil(x));
        long sum=w*(w+1);
        sum=sum/2;
        //System.out.println (w+"GDSGDS");
        while (sum%2!=k%2)
        {
            w++;
            sum=w*(w+1);
            sum=sum/2;
        }
        return (w);
    }
    static int knapSack(long W, int wt[], int val[], int n) 
     { 
        // Base Case 
    if (n <=0 || W == 0) 
        return 0; 
    if (wt[n-1] > W) 
       return knapSack(W, wt, val, n-1); 
    else 
    return Math.max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-2), knapSack(W, wt, val, n-1)); 
      } 
    static boolean index(int x, int y, int N, int M)
    {
        if (x>=0 && y>=0 && x<N && y<M)
        return (true);
        else
        return (false);
    }
    static boolean check (String a)
    {
        int len=a.length();
        char z;
        int l=0;
        int r=len-1;int p=0;
        while (l<=r && p==0)
        {
            if (a.charAt(l)==a.charAt(r))
            {l++;r--;}
            else 
            p=1;
        }
        if (p==0)
        return (true);
        else
        return (false);
    }
    static void inter(int c1,int c2,int c3,int c4)
    {
	        if (c3>c2 || c4<c1)
	        System.out.println ("No");
	        else
	        System.out.println (Math.max(c1,c3)+" "+Math.min(c2,c4));
    }
 //   static HashMap<Long, Long> h = new HashMap<Long, Long>();
    static void subsetsum(int d[], int N, int k)
    {
        int a[][] = new int[N+1][k+1];
        for (int x=0;x<=N;x++)
        a[x][0]=1;
        for (int x=1;x<=k;x++)
        a[0][x]=0;

        for (int x=1;x<=N;x++)
        {
            for(int y=1;y<=k;y++)
            {
               if (a[x-1][y]==1 || (y-d[x-1]>=0 && a[x-1][y-d[x-1]]==1))
               a[x][y]=1;
            }
        }
        //for (int x=0;x<=N;x++)
       ///  {
            // for (int y=0;y<=k;y++)
            // {
            //     System.out.print (a[x][y]+" ");
            // }
           //  System.out.println ();
         //}
        if (a[N][k]==1)
        System.out.println ("YES");
        else
        System.out.println ("NO");
    }
    static int coinsp(int A[], int M, int N)
    {
        int a[] = new int[N+1];
        a[0] = 1;
        for (int x=1;x<=N;x++)
        a[x]=0;
        for (int x=1;x<=M;x++)
        {
            for (int y=1;y<=N;y++)
            {
                if (y>=A[x-1])
                a[y]+=a[y-A[x-1]];
            }
        }
        return (a[N]);
    }
    static long kp(int v[], int c[], int C, int max)
    {
        int N=v.length;
        long d[] = new long[max*N+1];
        for (int x=1;x<=max*N;x++)
        d[x]=Integer.MAX_VALUE;
        //int b[] = new int[C+1];
        for (int x=0;x<N;x++)
        {
            for (int y=max*N;y>=0;y--)
            {
                if (y>=v[x])
                d[y]=Math.min(d[y],d[y-v[x]]+c[x]);
            }
        }
        long ans=0;
        for (int x=1;x<=max*N;x++)
        {
            if (d[x]<=C)
            ans=x;
        }
        return (ans);
    }
    static int d(int a[][], int N, int p)
    {
        if (N<0)
        return (0);
        else
        {
            int ans=Integer.MAX_VALUE;
            for (int x=1;x<=3;x++)
            {
                if (x==p)
                continue;
                else
                ans=Math.min(ans,a[N][x-1]+d(a,N-1,x));
            }
            return (ans);
        }
    }
    static boolean cck(String a)
    {
        int l=a.length();
        int c=l/2;
        int p=0;
        for (int x=0;x<c;x++)
        {
            if (a.charAt(x)==a.charAt(x+c))
            continue;
            else
            
            {p=1;break;}
        }
        if (p==0)
        return (true);
        else
        return (false);
    }
    static long an(long N)
    {
        return ((N*(N+1))/2);
    }
    static long a[][] = new long[1001][1001];
    static long M=1000000007;
    static void ncr()
    {
        for (int x=0;x<=1000;x++)
        {
            for (int y=0;y<=1000;y++)
            {
                if (y==0 || x==y)
                a[x][y]=1;
                else if (y>x)
                a[x][y]=0;
                else
                a[x][y]=(a[x-1][y]%M+a[x-1][y-1]%M)%M;
            }
        }
    }
    static HashMap<String, Integer> h = new HashMap<String, Integer>();
    static String A="";
   // ArrayList<ArrayList<Integer>> a1[] = new ArrayList[26];
	public static void main (String[] args) throws java.lang.Exception
	{
	    InputReader in = new InputReader(System.in);;
	    int T=in.readInt();
	    for (int Q=1;Q<=T;Q++)
	    {
	        int N=in.readInt();
	        String a=in.readString();
	        String b=in.readString();
	        ArrayList<Integer> ans = new ArrayList<Integer>();
	        for (int x=0;x<N;x++)
	        {
	            if (a.charAt(x)!=b.charAt(x) && x!=0)
	            {ans.add(x+1);ans.add(1);ans.add(x+1);}
	            else if (a.charAt(x)!=b.charAt(x) && x==0)
	            ans.add(x+1);
	        }
	        System.out.print (ans.size()+" ");
	        for (int x=0;x<ans.size();x++)
	        {
	            System.out.print (ans.get(x)+" ");
	        }
	        System.out.println ();
	    }
	}
private static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;
 
		public InputReader(InputStream stream) {
			this.stream = stream;
		}
 
		public int read() {
			if (numChars == -1) {
				throw new InputMismatchException();
			}
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}
 
		public int readInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9') {
					throw new InputMismatchException();
				}
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public String readString() {
			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 double readDouble() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			double res = 0;
			while (!isSpaceChar(c) && c != '.') {
				if (c == 'e' || c == 'E') {
					return res * Math.pow(10, readInt());
				}
				if (c < '0' || c > '9') {
					throw new InputMismatchException();
				}
				res *= 10;
				res += c - '0';
				c = read();
			}
			if (c == '.') {
				c = read();
				double m = 1;
				while (!isSpaceChar(c)) {
					if (c == 'e' || c == 'E') {
						return res * Math.pow(10, readInt());
					}
					if (c < '0' || c > '9') {
						throw new InputMismatchException();
					}
					m /= 10;
					res += (c - '0') * m;
					c = read();
				}
			}
			return res * sgn;
		}
 
		public long readLong() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9') {
					throw new InputMismatchException();
				}
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public boolean isSpaceChar(int c) {
			if (filter != null) {
				return filter.isSpaceChar(c);
			}
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
 
		public String next() {
			return readString();
		}
 
		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
 
	private static class OutputWriter {
		private final PrintWriter writer;
 
		public OutputWriter(OutputStream outputStream) {
			writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
		}
 
		public OutputWriter(Writer writer) {
			this.writer = new PrintWriter(writer);
		}
 
		public void print(Object... objects) {
			for (int i = 0; i < objects.length; i++) {
				if (i != 0) {
					writer.print(' ');
				}
				writer.print(objects[i]);
			}
			writer.flush();
		}
 
		public void printLine(Object... objects) {
			print(objects);
			writer.println();
			writer.flush();
		}
 
		public void close() {
			writer.close();
		}
 
		public void flush() {
			writer.flush();
		}
	}
}
class Pair implements Comparable<Pair>{
                            long a;
                            long b;
                            
                            Pair(long a,long b){
                                this.b = b;
                                this.a = a;
                               
                            }
                            public boolean equals(Object o) {
                                Pair p = (Pair)o;
                                return this.a == p.a && this.b == this.b;
                            }
                            public int hashCode(){
                                return Long.hashCode(a)*27 + Long.hashCode(b)*31;
                            }
                            public int compareTo(Pair p) {
                                if(this.a == p.a) {
                                    return Long.compare(this.b,p.b);
                                }
                                return Long.compare(this.a,p.a);
                            }
                        }