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:
//package com.company;


import com.sun.jdi.request.ThreadStartRequest;

import javax.print.attribute.standard.PrinterIsAcceptingJobs;
import javax.sound.midi.spi.SoundbankReader;
import java.awt.*;
import java.awt.image.AreaAveragingScaleFilter;
import java.io.*;
import java.math.BigInteger;
import java.net.Inet4Address;
import java.sql.Array;
import java.sql.SQLOutput;
import java.text.CollationElementIterator;
import java.util.*;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.logging.Logger;

public class Main implements Runnable {
    int size[];
    static int e9 = 1000000007;
    int max = Integer.MIN_VALUE;
    long max1 = Long.MIN_VALUE;
    long min1 = Long.MAX_VALUE;
    long fib[][];
    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;
        }
    }
    int parent[];
    int rank[];
    ArrayList<ArrayList<Integer>> arrayLists;
    long fib1[][];
    long r[];
    int n;
    int m;
    long co=0;
    long size1[];
    long v[];
    int arr[][];
    int u=0;
    HashMap<Long,Long> hashMap=new HashMap<>();
    ArrayList<Long> arrayList;
    public static void main(String[] args) throws IOException {
        new Thread(null,new Main(),"Main",1<<28).start();
    }

    public void run() {
        FastReader scanner = new FastReader();
//            Scanner scanner = new Scanner(System.in);
//            BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter printWriter = new PrintWriter(System.out);
        long t =scanner.nextLong();
        high:while (t-- > 0) {
            int n=scanner.nextInt();
            String s=scanner.next();
            String s1=scanner.next();
            char arr[]=s.toCharArray();
            int u=0;
            ArrayList<Integer> arrayList=new ArrayList<>();
            for (int i =0; i<s1.length(); i++) {
                if(s1.charAt(i)!=arr[i]){
                    arrayList.add(i+1);
                    arrayList.add(1);
                    arrayList.add(i+1);
                    arr[i]=s1.charAt(i);
                }
            }
            printWriter.print(arrayList.size()+" ");
            for (int i = 0; i < arrayList.size(); i++) {
                printWriter.print(arrayList.get(i)+" ");
            }
            printWriter.println();
        }
        printWriter.flush();
    }
    static long mod=1_000_000_007;
    public long lcm(long a,long b){
        return (a*b)/gcd(a,b);
    }
    public long mul(long a, long b) {
//        System.out.println(a+" "+b);
        return ((a)*(b));
    }
    public long fact(int x) {
        long ans=1;
        for (int i=2; i<=x; i++) ans=mul(ans, i);
        return ans;
    }
    public long fastPow(long base, long exp) {
        if (exp==0) return 1;
        long half=fastPow(base, exp/2);
        if (exp%2==0) return mul(half, half);
        return mul(half, mul(half, base));
    }
    public long modInv(long x) {
        return fastPow(x, mod-2);
    }
    public long nCk(int n, int k) {
        return mul(fact(n), mul(modInv(fact(k)), modInv(fact(n-k))));
    }
    public void parent(int n){
        parent=new int[n+1];
        size=new int[n+1];
        rank=new int[n+1];
        for (int i = 0; i <=n; i++) {
            parent[i]=i;
            rank[i]=0;
//            size[i]=1;
        }
    }
    public void union(int i,int j){
        int root1=find(i);
        int root2=find(j);
//            if(root1 != root2) {
//                parent[root2] = root1;
////                sz[a] += sz[b];
//            }
        if(root1==root2){
            return;
        }
        if(rank[root1]>rank[root2]){
            parent[root2]=root1;
            size[root1]+=size[root2];
        }
        else if(rank[root1]<rank[root2]){
            parent[root1]=root2;
            size[root2]+=size[root1];
        }
        else{
            parent[root2]=root1;
            rank[root1]+=1;
            size[root1]+=size[root2];
        }
    }
    public int find(int p){
        if(parent[p]!=p){
            if(parent[p]==-1){
                return parent[p];
            }
            parent[p]=find(parent[p]);
        }
        return parent[p];
    }
    public double dist(double x1,double y1,double x2,double y2){
        double e=(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
        double e1=Math.sqrt(e);
        return e1;
    }
    public void make(int p){
        parent[p]=p;
        rank[p]=1;
    }
    Random rand = new Random();
    public void sort(int[] a, int n) {
        for (int i = 0; i < n; i++) {
            int j = rand.nextInt(i + 1);
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
        Arrays.sort(a, 0, n);
    }
    public long gcd(long a,long b){
        if(b==0){
            return a;
        }
        return gcd(b,a%b);
    }
    //    public void dfs(ArrayList<Integer> arrayList){
//        for (int i = 0; i < arrayList.size(); i++) {
//            if(v1[arrayList.get(i)]==false){
//                v1[arrayList.get(i)]=true;
//                dfs(arrayLists.get(i));
//            }
//        }
//    }
    public double fact(double h){
        double sum=1;
        while(h>=1){
            sum=(sum%e9)*(h%e9);
            h--;
        }
        return sum%e9;
    }
    public long primef(double r){
        long c=0;
        long ans=1;
        long g=0;
        while(r%2==0){
            c++;
            r=r/2;
        }
        if(c>0){
            ans*=2;
        }
        c=0;
//            System.out.println(ans+" "+r);
        for (int i = 3; i <=Math.sqrt(r) ;i+=2) {
            g=0;
            while(r%i==0){
//                    System.out.println(i);
                c++;
                g++;
                r=r/i;
            }
            if(c>0){
                ans*=i;
            }
            c=0;
        }
        if(r>2){
            ans*=r;
        }
        return ans;
    }
    public long divisor(double r){
        long c=0;
//        if(n==3)
//            System.out.println(r+" "+n+" "+k+" "+"l");
        for (int i =2; i <=Math.sqrt(r); i++) {
            if(r%i==0){
                if(r/i==i){
                    c++;
                }
                else{
                    if(r/i<n){
                        c+=2;
                    }else{
                        c++;
                    }
                }
            }
        }
        return c;
    }
}
class Pair {
    long x;
    long y;
    int z;
    public Pair(long x,long y) {
        this.x = x;
        this.y = y;
//        this.z=z;
    }

//     @Override
//    public int hashCode() {
//        int hash = 37;
//        return this.x * hash + this.y;
//    }
//
//    @Override
//    public boolean equals(Object o1) {
//        if (o1 == null || o1.getClass() != this.getClass()) {
//            return false;
//        }
//        Pair o = (Pair) o1;
//        if (o.x == this.x && o.y == this.y) {
//            return true;
//        }
//        return false;
//    }
}
class Sorting implements Comparator<Pair> {
    public int compare(Pair p1, Pair p2) {
        if(p1.x==p2.x){
            return Long.compare(p1.y,p2.y);
        }else {
            return Long.compare(p1.x, p2.x);
        }
    }
}
class Edge{
    int s=0;
    int d=0;
    int c=0;
    public Edge(int s,int d,int c){
        this.s=s;
        this.d=d;
        this.c=c;
    }
}