Migrated from Lutece 517 置换与循环

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

任给两个$1$到$n$的排列，两个排列构成了一个双射（实际这就是一个置换）。经过交换，第一个排列总可以写为 $(1,2,\cdots ,n)$，记第$2$个排列为 $(b_1,b_2,\cdots ,b_n)$，则$1$映射为$b_1$，$2$映射为$b_2$，$\cdots$，$n$映射为$b_n$。实际上，一个置换可以写成一系列循环的积。举一个例子：$(1,2,3,4,5)$和$(4,2,1,3,5)$，$1$映射为$4$，$4$映射为$3$，而$3$又被映射为$1$，这是该置换的第一个循环$(1,4,3)$ ；$2$被映射为$2$，这是第二个循环$(2)$；$5$被映射为$5$，这是第三个循环$(5)$，所以该置换可以表示为$(1,4,3)(2)(5)$。 你的任务是对于任意给定的置换，把该置换表示为一系列循环的积。

由于循环$(1,4,3)$与循环$(4,3,1)$,$(3,1,4)$等价，我们要求输出循环时，总是以最小元素开始。另外，不同循环可以交换次序，为保证唯一，要求按循环的第一元素从小到大输出。

Input

有多组测试数据。输入的第一行是数据组数$T$($1<T\leq 200$)。每组数据的第一行是整数$n$($3\leq n\leq 150$)，表示下面两行分别是$1$到$n$的排列，第一行排列为$1, 2, \cdots, n$，两行中每个数后有一个空格。

Output

对应每组数据，输出一行该置换的循环积。

Samples

3
7
1 2 3 4 5 6 7 
6 1 7 2 5 3 4 
4
1 2 3 4 
4 3 1 2 
4
1 2 3 4 
1 3 2 4

(1,6,3,7,4,2)(5)
(1,4,2,3)
(1)(2,3)(4)

Resources

wxiaoping