Problem Statement

You are given strings $s$ and $t$ of length $N$ consisting of 0 and 1. Determine whether it is possible to make $s$ match $t$ by performing the following operation at least $0$ and at most $N+1$ times, and if possible, show one such sequence of operations.

Operation: Perform the following in order.

1. Choose integers $a$ and $b$ satisfying $1 \le a,b \le N$ and $|a-b|=1$
2. Append the $a$-th character from the beginning of $s$ to the end of $s$
3. Remove the $b$-th character from the beginning of $s$ and concatenate the remaining characters in their original order

You are given $T$ test cases; find the answer for each of them.

Constraints

• $1 \le T \le 10^{5}$
• $2 \le N \le 2 \times 10^{5}$
• $s$ and $t$ are strings of length $N$ consisting of 0 and 1.
• The sum of $N$ over all test cases is at most $2 \times 10^{5}$.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Each test case is given in the following format:

N
s
t

Output

Print the answers for the given test cases in the order they are given. If it is impossible to make $s$ match $t$ by performing the operation at least $0$ and at most $N+1$ times, print -1. If possible, first print the number of operations $K$, and on the $j$-th of the following $K$ lines, print the two integers $a_j$ and $b_j$ chosen in the $j$-th operation, separated by a space.