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.io.*;
public class Main
{   
    public static String changeAll(String str)
    {
        String temp="";
        for(int i=0;i<str.length();i++)
        if(str.charAt(i)=='1')
         temp=temp+"0";
        else temp=temp+"1";
        
        String temp2="";
        for(int i=temp.length()-1;i>=0;i--)
        {
            temp2=temp2+(temp.charAt(i)+"");
        }
        
        return temp2;
    }
    
    public static String changeFirst(String str)
    {
        String temp="";
        for(int i=0;i<str.length();i++)
        {
            if(i==0)
            {
                if(str.charAt(i)=='1')
                temp=temp+"0";
                else temp=temp+"1";
            }
            else temp=temp+(str.charAt(i)+"");
        }
        return temp;
    }
	public static void main(String[] args)throws IOException {
		FastReader kb=new FastReader();
        int t=kb.nextInt();
        while(t-->0)
        {
            int n=kb.nextInt();
            String str1=kb.next();
            String str2=kb.next();
            ArrayList<Integer> ans=new ArrayList<>();
            int i=str1.length()-1;
            while(str1.length()>0 && i>=0)
            {
                if(str1.charAt(i)==str2.charAt(i))
                {
                    str1=str1.substring(0,str1.length()-1);
                    str2=str2.substring(0,str2.length()-1);
                    i--;
                }
                else 
                {
                    if(str1.charAt(0)!=str2.charAt(i))
                    {
                        ans.add(str1.length());
                        str1=changeAll(str1);
                    }
                    else 
                     {
                         ans.add(1);
                         str1=changeFirst(str1);
                         ans.add(str1.length());
                         str1=changeAll(str1);
                     }
                }
                
                
            }
            System.out.print(ans.size()+" ");
                for(int j:ans)
                System.out.print(j+" ");
                System.out.println();
        }
	}
	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; 
        } 
    } 
  
}
/*
Admin Blues problem tcs codevita
A person, new to his job in a start-up, was given a task by his supervisor to prepare a
report where the user IDs (of all the employees) is a part of the report. He fetched the
user IDs from database and then used a spreadsheet function to concatenate them to
share it in email as text. However, while concatenating, he forgot to put a comma ,
in between the two user IDs
As a rule, user IDs of the portal should be minimum 4 characters and can only contain alphabets and cannot start or end with a vowel.

Supervisor knows about this rule and the number of employees in the department. Therefore, he tries to guess a possible set of user IDs from the given string (of user IDs in the email). You need to find the total no. of different set of user Ids that are possible given the number of employees in the department and the string of user IDs.

Constraints
1<Number of Employees<10
7<Length of user id string <51
Input Format
First Line contains an integer, which provides the Number of Employees in the
organization
Second Line contains a string of concatenated user ids
Output
Number of possibilities of user ID sets
If none are possible, print 0
Example Input 1
2
nonajklop
Output
1
Explanation
Since supervisor knows there are only 2 user IDs and they cannot start or end with a
vowel, there is only one possibility - nonaj and klop so there is only one probability
of the user ID sets.


Example Input 2
 3
 poppolfgopjduhqertol
Output
6
Explanation
Since supervisor knows there are only 3 user IDs and they cannot start or end with a
vowel, there are following possibilities -

poppol fgop jduhqertol
poppol fgopj duhqertol
poppol fgopjduh qertol 
poppolf gopjduh qertol
poppolf gopj duhqertol
poppolfgop jduh qertol
Here there are 6 possibilities.


*/