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.Collections;
import java.util.List;
import java.util.StringTokenizer;


public class C {
    public static FastReader fs = new FastReader();

    static PrintWriter out = new PrintWriter(System.out);

    static void solve() {
        StringBuffer output = new StringBuffer();
        int n = fs.nextInt();
        char s1 [] = fs.next().toCharArray();
        char s2 [] = fs.next().toCharArray();
        ArrayList<Integer> ans = new ArrayList<>();
        int j = 0;
        while(j < n){
            if(s1[j] == '1'){
                if(j!=0) ans.add(j);
                int k = j+1;
                while(k < n && s1[k] == s1[j])k++;
                ans.add(k);
                j = k;
            }
            else j++;
        }
        int current = '0';
        for(int i = n-1; i>=0; i--){
            if(s2[i] == current)continue;
            else{
                ans.add(i+1);
                current = (current == '0' ? '1' : '0');
            }
        }
        out.print(ans.size() + " ");
        for(Integer x : ans)out.print(x + " ");
        out.println();
    }

    public static void main(String[] args) {
        int t = 1;
        t = fs.nextInt();
        for(int cs = 1; cs <= t; cs++) {
            solve();
        }
        out.close();
    }

    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;
        }
    }

    static int ceil(int x,int y) {
        return (x % y == 0 ? x / y : (x / y +1));
    }

    static long ceil(long x,long y) {
        return (x % y == 0 ? x / y : (x / y +1));
    }

    static int max(int x,int y) {
        return Math.max(x, y);
    }

    static int min(int x,int y) {
        return Math.min(x, y);
    }

    static long max(long x,long y) {
        return Math.max(x, y);
    }

    static long min(long x,long y) {
        return Math.min(x, y);
    }

    static int min(int a []) {
        int x = 1_000_000_00_9;
        for(int i = 0; i<a.length; i++)x = min(x,a[i]);
        return x;
    }

    static int max(int a []) {
        int x = -1_000_000_00_9;
        for(int i = 0; i<a.length; i++)x = max(x,a[i]);
        return x;
    }

    static long min(long a []) {
        long x = (long)3e18;
        for(int i = 0; i<a.length; i++)x = min(x,a[i]);
        return x;
    }

    static long max(long a []) {
        long x = -(long)3e18;
        for(int i = 0; i<a.length; i++)x = max(x,a[i]);
        return x;
    }

    static int power(int x,int y) {
        int res = 1;
        while(y > 0) {
            if( y % 2 == 1)res = (res * x);
            y >>= 1;
            x = (x * x);
        }
        return res;
    }

    static long power(long x,long y) {
        long res = 1;
        while(y > 0) {
            if( y % 2 == 1)res = (res * x);
            y >>= 1;
            x = (x * x);
        }
        return res;
    }

    static long power(long x,long y,long mod) {
        long res = 1;
        x %= mod;
        while(y > 0) {
            if( y % 2 == 1)res = (res * x) % mod;
            y >>= 1;
            x = (x * x) % mod;
        }
        return res;
    }

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

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

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

    static void reverselongsort(long [] a) {
        List<Long> temp = new ArrayList<Long>();
        for(int i = 0; i<a.length; i++)temp.add(a[i]);
        Collections.sort(temp);
        Collections.reverseOrder();
        for(int i = 0; i<a.length; i++)a[i] = temp.get(i);
    }

    static void intpairsort(intpair [] a) {
        List<intpair> temp = new ArrayList<intpair>();
        for(int i = 0; i<a.length; i++)temp.add(a[i]);
        Collections.sort(temp,(p1,p2) -> {
            if(p1.x == p2.x) return p1.y >= p2.y ? -1 : 1;
            else return p1.x > p2.x ? -1 : 1;
        });
        for(int i = 0; i<a.length; i++)a[i] = temp.get(i);
    }

    static void longpairsort(longpair [] a) {
        List<longpair> temp = new ArrayList<longpair>();
        for(int i = 0; i<a.length; i++)temp.add(a[i]);
        Collections.sort(temp,(p1,p2) -> {
            if(p1.x == p2.x) return p1.y >= p2.y ? -1 : 1;
            else return p1.x > p2.x ? -1 : 1;
        });
        for(int i = 0; i<a.length; i++)a[i] = temp.get(i);
    }

    static class intpair{
        public int x;
        public int y;

        intpair(int a,int b){
            this.x = a;
            this.y = b;
        }

        intpair(){}
    }

    static class longpair{
        public long x;
        public long y;

        longpair(long a,long b){
            this.x = a;
            this.y = b;
        }

        longpair(){}
    }

    static class data{
        public long sum;

        data(long val){
            this.sum = val;
        }

        data(){}

        data combine(data l, data r) {
            data res = new data();
            res.sum = l.sum + r.sum;
            return res;
        }
    }

    static class Seg_Tree extends data{
        public int n;
        data [] seg;

        Seg_Tree(int sz){
            this.n = sz;
            seg = new data[4*n+4];
        }

        void build(long a[], int v, int tl, int tr) {
            if (tl == tr) {
                seg[v] = new data(a[tl]);
            } else {
                int tm = (tl + tr) / 2;
                build(a, v*2, tl, tm);
                build(a, v*2+1, tm+1, tr);
                seg[v] = combine(seg[v*2],seg[v*2+1]);
            }
        }

        void update(int v, int tl, int tr, int pos, long new_val) {
            if (tl == tr) {
                seg[v] = new data(new_val);
            } else {
                int tm = (tl + tr) / 2;
                if (pos <= tm)
                    update(v*2, tl, tm, pos, new_val);
                else
                    update(v*2+1, tm+1, tr, pos, new_val);
                seg[v] = combine(seg[v*2],seg[v*2+1]);
            }
        }

        data query(int v, int tl, int tr, int l, int r) {
            if (l > r)
                return new data(0);
            if (l == tl && r == tr)
                return seg[v];
            int tm = (tl + tr) / 2;
            return combine(query(v*2, tl, tm, l, min(r, tm)),query(v*2+1, tm+1, tr, max(l, tm+1), r));
        }
    }

    static class Bit_Tree{
        static int n;
        static int [] bit;

        Bit_Tree(int sz){
            Bit_Tree.n = sz;
            Bit_Tree.bit = new int[n+1];
        }

        static int child(int x) {
            return x + (x & (-x));
        }

        static int parent(int x) {
            return x - (x & (-x));
        }

        static void build(int [] a) {
            for(int i = 0; i<a.length; i++) {
                int start = i+1;
                while(start <= n) {
                    bit[start] += a[i];
                    start = child(start);
                }
            }
        }

        static void update(int idx,int new_val) {
            idx += 1;
            while(idx <= n) {
                bit[idx] += new_val;
                idx = child(idx);
            }
        }

        static int query(int right) {
            int res = 0;
            while(right > 0) {
                res += bit[right];
                right = parent(right);
            }
            return res;
        }

        static int query(int left,int right) {
            return query(right) - query(left-1);
        }
    }

    public static int gcd(int a, int b)
    {
        BigInteger b1 = BigInteger.valueOf(a);
        BigInteger b2 = BigInteger.valueOf(b);
        BigInteger gcd = b1.gcd(b2);
        return gcd.intValue();
    }

    public static long gcd(long a, long b)
    {
        BigInteger b1 = BigInteger.valueOf(a);
        BigInteger b2 = BigInteger.valueOf(b);
        BigInteger gcd = b1.gcd(b2);
        return gcd.longValue();
    }
}