You are given two permutations $$$p_1,p_2,\ldots,p_n$$$ and $$$q_1,q_2,\ldots,q_n$$$ of length $$$n$$$. In one operation, you can select two integers $$$1\leq i,j\leq n,i\neq j$$$ and swap $$$p_i$$$ and $$$p_j$$$. The cost of the operation is $$$\min (|i-j|,|p_i-p_j|)$$$.

Find the minimum cost to make $$$p_i = q_i$$$ hold for all $$$1\leq i\leq n$$$ and output a sequence of operations to achieve the minimum cost.

A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

The first line of input contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of input test cases.

The first line of each test case contains one integer $$$n$$$ ($$$2 \le n \le 100$$$) — the length of permutations $$$p$$$ and $$$q$$$.

The second line contains $$$n$$$ integers $$$p_1,p_2,\ldots,p_n$$$ ($$$1\leq p_i\leq n$$$) — the permutation $$$p$$$. It is guaranteed that $$$p_1,p_2,\ldots,p_n$$$ is a permutation of $$$1,2,\ldots,n$$$.

The third line contains $$$n$$$ integers $$$q_1,q_2,\ldots,q_n$$$ ($$$1\leq q_i\leq n$$$) — the permutation $$$q$$$. It is guaranteed that $$$q_1,q_2,\ldots,q_n$$$ is a permutation of $$$1,2,\ldots,n$$$.

It is guaranteed that the sum of $$$n^3$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output the total number of operations $$$k$$$ ($$$0\le k\le n^2$$$) on the first line. Then output $$$k$$$ lines, each containing two integers $$$i,j$$$ ($$$1\le i,j\le n$$$, $$$i\neq j$$$) representing an operation to swap $$$p_i$$$ and $$$p_j$$$ in order.

It can be shown that no optimal operation sequence has a length greater than $$$n^2$$$.

Note

In the second test case, you can swap $$$p_1,p_3$$$ costing $$$\min(|1-3|,|1-3|)=2$$$. Then $$$p$$$ equals $$$q$$$ with a cost of $$$2$$$.

In the third test case, you can perform the following operations:

Initially, $$$p=[2,1,4,3]$$$.

Swap $$$p_1,p_4$$$ costing $$$\min(|1-4|,|2-3|)=1$$$, resulting in $$$p=[3,1,4,2]$$$.
Swap $$$p_2,p_4$$$ costing $$$\min(|2-4|,|1-2|)=1$$$, resulting in $$$p=[3,2,4,1]$$$.
Swap $$$p_1,p_3$$$ costing $$$\min(|1-3|,|3-4|)=1$$$. Then $$$p$$$ equals $$$q$$$ with a cost of $$$3$$$.

✓	#	Name		✎	Rating↕	Solved↕
	2062G	Permutation Factory flows geometry graph matchings graphs			3500	203
	1949I	Disks dfs and similar geometry graph matchings graphs			1800	2.8k

Problemset