C. Changing Game
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Welcome to Changing Game! In this game, you are given an integer array $$$A$$$ of $$$n$$$ distinct values $$$a_1, a_2, \cdots, a_n$$$.

You are allowed to do some operations on array $$$A$$$. In each operation you can select an element from $$$A$$$ and replace it with an integer $$$c$$$. Note that you need to keep all elements of $$$A$$$ distinct after each operation.

Now, you are given an integer array $$$B = \left[b_1, b_2, \cdots, b_n\right]$$$ which derives from $$$A$$$ through some number of operations by Master Yi. Could you restore the operation sequence performed by Master Yi that produces $$$B$$$ from $$$A$$$? It sounds too easy to do this job. In order to increase the difficulty of this problem, Master Yi recommended that you need to find the most optimal one. In other words, you should find the minumum number of operation(s) that produces $$$B$$$ from $$$A$$$.

Input

You need to process $$$t$$$ test cases.

The first line contains an integer $$$t\ (1\le t\le 100)$$$ — the number of test cases. Then descriptions of $$$t$$$ test cases follow.

  • The first line of each test case contains one integer $$$n\ (1\le n\le 100\ 000)$$$ — the length of the given arrays $$$A$$$ and $$$B$$$.
  • The second line contains $$$n$$$ integers $$$a_1,a_2\cdots,a_n\ (1\le a_i\le 1\ 000\ 000\ 000)$$$ — the elements of array $$$A$$$ in order. It's guaranteed that all elements in $$$A$$$ are distinct.
  • The third line contains $$$n$$$ integers $$$b_1,b_2,\cdots,b_n\ (1\le b_i\le 1\ 000\ 000\ 000)$$$ — the elements of array $$$B$$$ in order. It's guaranteed that all elements in $$$B$$$ are distinct.

It is guaranteed that the sum of the length $$$n$$$ for all test cases does not exceed $$$2\ 000\ 000$$$.

Output

For each test case, you should print several lines as follow.

  • The first line of each test case should contain one integer $$$m$$$ — the the minimum number of operation(s).
  • Then the next $$$m$$$ line(s), each line should contain $$$2$$$ integers $$$p\ (1\le p\le n)$$$ and $$$c\ (1\le c\le 1\ 000\ 000\ 000)$$$ — to choose the position $$$p_i$$$ to modify $$$a_{p_i}\leftarrow c_i$$$ in $$$i$$$-th operation.

If there are multiple answers, you can print any of them.

Example
Input
1
5
1 2 3 4 5
2 3 4 5 6
Output
5
5 6
4 5
3 4
2 3
1 2