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.lang.*; 
    import java.io.*; 
    import java.util.*;
    public class JavaApplication185 {
     
        /**
         * @param args the command line arguments
         */
        public static void main(String[] args) {
            // TODO code application logic here
            Scanner sc=new Scanner(System.in);
            int t=sc.nextInt();
            while(t--!=0)
            {
               int n=sc.nextInt();
              String s1=sc.next();
              String s2=sc.next();
              Vector<Integer> v=new Vector<>();
              int count=0;
              StringBuilder ans=new StringBuilder();
              for(int i=n-1;i>=0;i--)
              {
                  
                  if(s1.charAt(i)!=s2.charAt(i))
                  {  count++;
                     // System.out.println(i);
                   if(s1.charAt(i)==s1.charAt(0))
                   { //System.out.println("1");
                       String s3=s1.substring(0,i+1);
                       String s5=s1.substring(i+1);
                      // System.out.println(s3);
                       char h[]=s3.toCharArray();
                       StringBuilder sb=new StringBuilder();
                       for(int l=0;l<h.length;l++)
                       {
                           if(h[l]=='1')
                               h[l]='0';
                           else
                               h[l]='1';
                           sb.append(h[l]);
                                
                       }
                         sb= sb.reverse(); 
                         s3=sb.toString();;
                     
                       
                       
                       
                       s1=s3+s5;
                  int k=i+1;
                       ans.append(k+" ");
                   }
                   else
                   {
                       int k=0;
                       for(int j=i-1;j>=0;j--)
                       {
                           if(s1.charAt(i)!=s1.charAt(j))
                           {
                            k=j;
                            break;
                           }
                       }
                       String s3=s1.substring(0,k+1);
                       String s5=s1.substring(k+1);
                      // System.out.println(s3+" s5"+s5);
                       //System.out.println(s3);
                       char h[]=s3.toCharArray();
                       StringBuilder sb=new StringBuilder();
                       for(int l=0;l<h.length;l++)
                       {
                           if(h[l]=='1')
                               h[l]='0';
                           else
                               h[l]='1';
                           sb.append(h[l]);
                                
                       }
                     
                       sb= sb.reverse(); 
                         s3=sb.toString();;
                      // System.out.println(s3);
                     //  System.out.println(s3+"else");
                      
                       
                     
                       s1=s3+s5;
                       
                   k++;
                          ans.append(k+" ");
                       i++;
                   }
                   // System.out.println(s1+"yes");
                  }
                 
              }
             // System.out.println(s1+ " "+s2);
              System.out.println(count+" "+ans);
            }
        }
        
    }