K. Permutations

Известно, что любую перестановку можно единственным образом представить в виде произведения непересекающихся циклов. При этом само разложение можно записать множеством различных способов, например:
421365=(2)(143)(56)=(431)(65)(2)=…
Рассказывают, что в XIX веке два известных байтландских математика в своей переписке, посвящённой комбинаторным задачам, использовали следующий способ кодирования перестановок: математик A записывал перестановку в виде произведения циклов, после чего убирал все скобки и отправлял получившуюся запись математику B. Который, в свою очередь, восстанавливал лексикографически наибольшую из возможных исходных перестановок.
К сожалению, сохранились только письма от A к B. Ваша задача — написать программу, которая бы повторяла то, что делал B, то есть по записи в виде произведения перестановок с убранными скобками восстанавливала бы исходную перестановку, а если вариантов восстановления несколько — выбирала бы лексикографически максимальную.
Формат ввода
Первая строка входа содержит одно целое число T (1≤T≤210) — количество тестовых примеров.
Каждый тестовый пример состоит из двух строк. Первая строка задаёт длину перестановки N (1≤N≤105). Вторая строка содержит
N различных целых чисел от 1 до N — запись разложения перестановки в циклы с убранными скобками.
Гарантируется, что во входе не более, чем для 10 тестовых примеров n>1000.
Тестовый пример :

Ввод
2
6
2 1 4 3 5 6
3
3 2 1
Вывод
4 2 5 3 6 1
3 1 2
буду благодарен , если скажете хотя бы как это решать , потому что я даже не представляю

0