Palm Island

Tove is playing a card game. She has $n$ cards, each with a unique number from $1, 2, \dots, n$. In this game, Tove can perform operations on the deck. Assuming the order of the deck from top to bottom is $p_1, p_2, \dots, p_n$ (a permutation), each operation must be one of the following two types:

1. Move the top card to the bottom of the deck, so the deck order becomes $p_2, p_3, \dots, p_n, p_1$.
2. Move the second card from the top to the bottom of the deck, so the deck order becomes $p_1, p_3, \dots, p_n, p_2$.

Given the initial order of Tove's deck (from top to bottom) as $a_1, a_2, \dots, a_n$, Tove wants to change the deck order to $b_1, b_2, \dots, b_n$ through a sequence of operations. Please construct an operation sequence to help Tove achieve this change.

Tove is impatient, so the number of operations should not exceed $n^2$.

Input

The first line contains an integer $T$, representing the number of test cases.

• The first line of each test case contains an integer $n$ ($3 \le n \le 1000$), representing the number of cards Tove has.
• The second line contains $n$ integers $a_1, a_2, \dots, a_n$, representing the initial permutation of the deck.
• The third line contains $n$ integers $b_1, b_2, \dots, b_n$, representing the target permutation of the deck.

The sum of $n$ over all $T$ test cases does not exceed $1000$.

Output

For each test case:

• Output a string $s_1s_2 \dots s_k$ ($s_i \in \{1, 2\}, 1 \le i \le k$) as the operation sequence. The length of the string should not exceed $n^2$, otherwise it will be judged as "Wrong Answer".
• If there are multiple solutions, output any one of them.

Examples

Input 1

2
3
1 2 3
2 3 1
4
1 2 3 4
2 1 3 4

Output 1

1
112212

Note

• If $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$ are identical in a test case, outputting an empty string is allowed, but in this case, an empty line must be printed.
• Do not add extra spaces at the end of the line, otherwise it will be judged as "Wrong Answer".