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.*;
import java.math.*;
import java.util.regex.*;

public class Main
{ 	
	public static void main(String[] args)throws Exception
	{ 	
	    /*
		Samples:-
		0
		1
		1 1
		
		00
		11
		3 1 2 1
		
		0011
		0001
		3 3 1 3
		*/
	    Reader reader = new Reader();
		reader.readLine();
		int t = reader.readInt(0);
		
		while(t-->0)
		{
			reader.readLine();
			int len = reader.readInt(0);
			
			reader.readLine();
			String a = reader.readString(0);
			
			reader.readLine();
			String b = reader.readString(0);
			
			StringBuilder res = new StringBuilder();
			int totalCount=0;
			
			for(int i=0;i<len;++i)
			{
				if(a.charAt(i)!=b.charAt(i))
				{
					if(i==0)
					{
						++totalCount;
						res.append(1).append(" ");
					}
					else
					{
						totalCount+=3;
						res.append(i+1).append(" ").append(1).append(" ").append(i+1).append(" ");
					}
				}
			}
			
			System.out.println(String.format("%d %s",totalCount,res.toString().trim()));
		}
		
		reader.close();
	}
}

class Pair
{
	int index;
	int level;

	public Pair(int index, int level)
	{
		this.index = index;
		this.level = level;
	}

	@Override
	public String toString()
	{
		return index + " " + level;
	}

}

class Reader
{     
    private BufferedReader reader; 
    private String line[];     

    public Reader()     
    {         
        reader = new BufferedReader(new InputStreamReader(System.in));     
    }     

    public String[] getLine()     
    {         
        return line;     
    }     

    public boolean readLine()     throws IOException 
    {         
        String str = reader.readLine();
        if (str == null || str.isEmpty())
            return false;
        line = line = str.split(" ");
        return true;
    }    

    public List<Integer> getIntegersList()
    {
        List<Integer> res = new ArrayList<>();
        for (String str:line)
            res.add(Integer.parseInt(str));
        return res;

    }

	public Set<Integer> getIntegersSet()
    {
        Set<Integer> res = new HashSet<>();
        for (String str:line)
            res.add(Integer.parseInt(str));
        return res;

    }

	public List<Long> getLongsList()
    {
        List<Long> res = new ArrayList<>();
        for (String str:line)
            res.add(Long.parseLong(str));
        return res;

    }

    public int readInt(int pos)throws IOException     
    {         
        return Integer.parseInt(line[pos]);     
    }     

    public double readDouble(int pos)throws IOException     
    {         
        return Double.parseDouble(line[pos]);     
    }     

    public long readLong(int pos)throws IOException 
    {         
        return Long.parseLong(line[pos]); 
    }     

    public String readString(int pos)throws IOException     
    {         
        return line[pos];     
    }     

    public void close()throws IOException 
    {         
        reader.close();     
    }
}