You are given two binary strings $s$ and $t$, each of the same length $n$. You are allowed to perform the following operation:

• Pick indices $l$, $r$ ($1 \le \color{red}{l \lt r} \le n$) such that substring $s_{l,r}$ is a palindrome and flip all bits in substring $s_{l,r}$.

The goal is to finally make $s$ equal to $t$, performing any of the above operations at most $2n$ times (possibly none).

A substring $s_{l,r}$ of a string $s$ is the contiguous sequence of characters starting from index $l$ and ending at index $r$ (both inclusive), where $1 \leq l \lt r \leq |s|$. Here $|s|$ denotes the length of the string $s$.

A string is a palindrome if it reads the same forwards and backwards. For example, the strings 101 and 00 are palindromes, while 10 is not.

Flipping all bits in a substring means changing each 0 to 1 and each 1 to 0 in that substring. For example, flipping the substring 101 results in 010.

Input

Each test contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 5\cdot 10^3$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($4 \le n \le 100$) — the length of the strings $s$ and $t$.

The next two lines of each test case contain the binary strings $s$ and $t$, respectively.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $5\cdot 10^5$.

Output

For each test case, if it is impossible to achieve the goal, print $-1$.

Otherwise, the first line should contain an integer $k$ ($0 \leq k \leq 2n$) — the number of operations.

For each of the next $k$ lines, print two integers $l, r$ ($1 \leq l \lt r \leq n$) — the indices you choose in each operation. Note that $s_{l,r}$ must be a palindrome at this stage.

Note

For the first test case:

• Initially, $s = \mathtt{01011}$ and $t = \mathtt{10000}$.
• First, we choose $l=1$ and $r=3$. This is a valid operation since $s_{1,3} = \mathtt{010}$ is a palindrome. After flipping $s_{1,3}$, $s = \mathtt{10111}$.
• Then, we choose $l=3$ and $r=5$. This is a valid operation since $s_{3,5} = \mathtt{111}$ is a palindrome. After flipping $s_{3,5}$, $s = \mathtt{10000}$.
• Now, $s$ is equal to $t$.

For the second test case:

• Initially, $s = \mathtt{1010101}$ and $t = \mathtt{0101010}$.
• First, we choose $l=1$ and $r=7$. This is a valid operation since $s_{1,7} = \mathtt{1010101}$ is a palindrome. After flipping $s_{1,7}$, $s = \mathtt{0101010}$.
• Now, $s$ is equal to $t$.

For the third test case:

• Initially, $s$ is equal to $t$. No operations are needed.