## PERMCYC - Permutation Cycle Decomposition

no tags

Note: This is the companion problem to the language-restricted Peculiar Permutivores. The contraints here are higher and the cluster is faster to allow better speed comparison, but otherwise it is the same problem.

Given some permutations, please print the unique cycle decomposition (up to ordering and rotations), excluding fixed points, and using the symbol "e" to denote the empty product.

### Input

The first line contains an integer T (1 ≤ T ≤ 50000). Then follow 2T lines, representing T test cases. The first line of each test case contains an integer N (1 ≤ N ≤ 50), and the second line contains a permutation of [1..N] as a space-separated list of N integers.

### Output

T lines containing the disjoint cycle decomposition of the corresponding permutation. Any correct answer is acceptable.

### Example

Input:

```5
3
1 2 3
3
2 1 3
4
2 1 4 3
9
3 8 9 4 1 7 6 2 5
9
3 8 9 4 1 7 6 2 5
```

Output:

```e
(1 2)
(1 2)(3 4)
(1 3 9 5)(2 8)(6 7)
(2 8)(9 5 1 3)(7 6)
```