Toph 正在玩一个纸牌游戏。她有 $n$ 张牌，每张牌上都有一个唯一的数字 $1, 2, \dots, n$。在这个游戏中，Toph 可以对牌堆进行操作。假设从牌堆顶到牌堆底的牌依次为 $p_1, p_2, \dots, p_n$（一个排列），那么每次操作必须是以下两种情况之一：

1. 将最顶部的牌放到牌堆底，即将牌堆顺序变为 $p_2, p_3, \dots, p_n, p_1$。
2. 将从顶部数第二张牌放到牌堆底，即将牌堆顺序变为 $p_1, p_3, \dots, p_n, p_2$。

现在，已知 Toph 牌堆的初始顺序（从顶到底）为 $a_1, a_2, \dots, a_n$，Toph 希望经过若干次操作后，将牌堆顺序变为 $b_1, b_2, \dots, b_n$。请构造一个操作序列来帮助 Toph 实现这一变化。

Toph 没有耐心，因此操作次数不应超过 $n^2$。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。 对于每个测试用例： 第一行包含一个整数 $n$ ($3 \le n \le 1000$)，表示 Toph 的牌数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示初始时牌堆的排列顺序。 * 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$，表示目标牌堆的排列顺序。

保证所有测试用例中 $n$ 的总和不超过 $1000$。

输出格式

对于每个测试用例： 输出一行，包含一个字符串 $s_1s_2 \dots s_k$ ($s_i \in \{1, 2\}, 1 \le i \le k$) 作为你的操作序列。 操作序列的长度不能超过 $n^2$，否则将得到“Wrong Answer”。 * 如果存在多种解，输出其中任意一个即可。

样例

输入 1

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

输出 1

1
112212

说明

如果在一个测试用例中 $a_1, a_2, \dots, a_n$ 与 $b_1, b_2, \dots, b_n$ 相同，输出空字符串是可以的。但在这种情况下，你仍然需要输出一个空行。

不要在行末添加多余的空格，否则将得到“Wrong Answer”判决。