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.*;

 
 public class Main	{
	 static class query implements Comparable<query>{
		 int a, b, ind;
		 public query(int x, int y, int z) {a = x; b = y; ind = z;}
		 public int compareTo(query q) {
			 return Integer.compare(b, q.b);
		 }
	 }
   static class Pair implements Comparable<Pair>{

	   int a;
	   int b;
//	   int ind;
//	   public Pair(int x, long y) {a = x;b=y;}
	   public Pair(int x, int y) {a = x;b=y;}
//	   public Pair(int x,int y, int z){a=x;b=y;ind = z;}
	   public int compareTo(Pair p){
		   return b - p.b;
	   }
//		@Override
//		public int hashCode() {
//			final int prime = 31;
//			int result = 1;
//			result = prime * result + a;
//			result = prime * result + b;
//		   
//			return result;
//		}
//		@Override
//		public boolean equals(Object obj) {
//			Pair cur = (Pair)obj;
//			if((a==cur.a && b==cur.b))return true;
//			return false;
//		}
 }
  static class cell{
	  int a, b;
	  public cell(int x, int y) {
		  a = x;
		  b = y;
	  }
  }
static class TrieNode{
	TrieNode left, right;
	int cnt;
	public TrieNode() {
		cnt = 0;
	}
}
  public static int gcd(int a,int b)
  {
    if(a<b)
      return gcd(b,a);
    if(b==0)
      return a;
    return gcd(b,a%b);
    
  }
  static int lcm(int a,int b) {
	  return  a*b / (int)gcd(a,b);
  }
  
   
    public static void main(String[] args) throws Exception {
       new Thread(null, null, "Anshum Gupta", 99999999) {
            public void run() {
                try {
                    solve();
                } catch(Exception e) {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }.start();
    }

static long pow(long x,long y){
    if(y == 0)return 1;
    if(y==1)return x;
    long a = pow(x,y/2);
    a = (a*a)%mod;
    if(y%2==0){
        return a;
    }
    return (a*x)%mod;
}

static final long mxx = (long)(1e18+5);
static final int mxN = (int)(1e2 + 5);
static final int mxV = (int)(2e5);
static final long mod = (long)(1e9+7); //998244353;//
static long[]fact,inv_fact;
static long my_inv(long a) {
	return pow(a,mod-2);
}
static long bin(int a,int b) {
	if(a < b || a<0 || b<0)return 0;
    return ((fact[a]*inv_fact[a-b])%mod * inv_fact[b])%mod;
}
	
static void make_facts() {
  fact=new long[mxN];
  inv_fact = new long[mxN];
  fact[0]=inv_fact[0]=1L;
  for(int i=1;i<mxN;i++) {
	   fact[i] = (i*fact[i-1]);//%mod;
//	   inv_fact[i] = my_inv(fact[i]);
  }
}
static void lazy(int st, int e, int tn) {
	if(lazy[tn] != INF) {
		tree[tn] = Math.min(tree[tn], lazy[tn]);
		if(st != e) {
			lazy[2*tn] = Math.min(lazy[2*tn], lazy[tn]);
			lazy[2*tn+1] = Math.min(lazy[2*tn+1], lazy[tn]);
		}
		lazy[tn] = INF;
	}
}
static void update(int ind, int val, int st, int e, int tn) {
	if(st == e) {
		tree[tn] = val;
		return;
	}
	int mid = (st + e) >> 1;	
  	if(ind <= mid)
		update(ind, val, st, mid, 2*tn);
  	else
		update(ind, val, mid+1, e, 2*tn+1);
	tree[tn] = Math.min(tree[2*tn], tree[2*tn+1]);
}
static int query(int l, int r, int st, int e, int tn) {
	if(st > r || e < l)return INF;
	
	if(st >= l && e <= r) {
		return tree[tn];
	}

	int mid = (st + e) >> 1;
	int x = query(l, r, st, mid, 2 * tn);
	int y = query(l, r, mid+1, e, 2 * tn + 1);
	return Math.min(x, y);
}
static int[]tree, lazy;
static final int INF = (int)1e9+5;
static ArrayList<ArrayList<Integer>> adj;
static boolean[]vis;
static int n, m, res;
static String a, b;
 public static void solve() throws Exception {
   // solve the problem here
   MyScanner s = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out), true);
        int tc = s.nextInt();
        
//	        make_facts(); 
     
        while(tc-->0){
        	n = s.nextInt();
        	a = s.next();
        	b = s.next();
        	a += "0";
        	b += "0";
//        	out.println(a.length() + " " + b.length());
        	ArrayList<Integer> ans = new ArrayList<Integer>();
        	ArrayList<Integer> tmp = new ArrayList<Integer>();
        	for(int i=1; i<=n; i++) {
        		if(a.charAt(i) != a.charAt(i-1))ans.add(i);
        		if(b.charAt(i) != b.charAt(i-1))tmp.add(i);
        	}
        	Collections.reverse(tmp);
        	for(int x : tmp) {
        		ans.add(x);
        	}
        	out.print(ans.size());
        	for(int x : ans) {
        		out.print(" " + x);
        	}out.println();
        }
        	
           
        out.flush();
}
 
     
 
 
 
    //-----------PrintWriter for faster output---------------------------------
    public static PrintWriter out;
 
    //-----------MyScanner class for faster input----------
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;
 
        public MyScanner() {
            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;
        }
    }
    //--------------------------------------------------------
}