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.
#!/usr/local/bin/python3
"""
You are given two strings A,B of length n.
These strings consist of '0' and '1'.
During one operation, you can:
    - Select a prefix of A, invert the bits in that prefix, and reverse the order of the bits in that prefix.
Easy: It can be proven that it's always possible to transform A to B within 3n operations.
Hard: It can be proven that it's always possible to transform A to B within 2n operations.
Please give an order of operations to fulfill this goal.

ex:
n=5
A=10101
B=11110

Is invert->reverse the same as reverse->invert?
reverse->invert: 110100 -> 001011 -> 110100
invert->reverse: 110100 -> 001011 -> 110100
^ In this case, reverse = invert

When is reverse != invert?
reverse->invert: 11001010 -> 01010011 -> 10101100
invert->reverse: 11001010 -> 00110101 -> 10101100
I think in general, it doesn't matter in what order you do the two ops.
Since you'll always end up inverting the same bit at the same location.

If the string is a palindrome, you'll end up just inverting all elements.

How can you prove that you'll always end up with B in 3n operations?

For these two problems, we can just make a brute force and look for a pattern
    -
Observations:
    - Lots of things like [n,1,n] and [1,n,1]

Just start from the end and go backwards! If you see an i s.t. A[i] != B[i], then pick i+1


If A[0] == A[i], then add i+1
Otherwise, pick the first j s.t. A[i] == A[j]. Do j+1, and then i
If j == i, then finish

Actually, I don't even need to do this.
I can just flip the first bit since I choose size 1. Then, I can do i+1.
"""

def apply(A, p):
    A[:p] = reversed(A[:p])
    for i in range(p):
        if A[i] == '1':
            A[i] = '0'
        else:
            A[i] = '1'

def brute(n,A,B):
    result = []
    for i in range(n-1,0,-1):
        if A[i]!=B[i]:
            if A[0]!=A[i]:
                result.append(1)
                apply(A,1)
            result.append(i+1)
            apply(A,i+1)
    if A[0]!=B[0]:
        result.append(1)
        apply(A,1)
    return result

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        A = list(input())
        B = list(input())
        #CHANGE
        result = brute(n,A,B)
        print(f"{len(result)} {' '.join(str(x) for x in result)}")

main()

