Saul Goodman 是世界上最好的律师。他坚信在被证明有罪之前，这个国家的每一个人都是清白的。然而，Saul 的一位客户却并非如此清白。

Saul 需要为他的辩护建立一个可靠的故事。共有 $n$ 个事件，编号从 $1$ 到 $n$。Saul 需要想出一个这些事件发生的顺序 $q_1, q_2, \dots, q_n$。然而，他的客户记忆力很差！如果 Saul 告诉他要记住事件的排列 $(q_1, q_2, \dots, q_n)$，他会记住排列 $(p_{q_1}, p_{q_2}, \dots, p_{q_n})$，其中 $(p_1, p_2, \dots, p_n)$ 是一个（固定的）从 $1$ 到 $n$ 的整数排列。

Saul 希望他们的排列尽可能一致：他想要最大化 $LCS((q_1, q_2, \dots, q_n), (p_{q_1}, p_{q_2}, \dots, p_{q_n}))$ 的值。请帮助他找到一个能使该值最大化的排列 $(q_1, q_2, \dots, q_n)$！如果存在多个这样的排列，输出其中任意一个即可。

这里 $LCS(a, b)$ 表示序列 $a$ 和 $b$ 的最长公共子序列的长度。例如，$LCS((1, 3, 4, 2, 5), (3, 1, 2, 4, 5)) = 3$，其中一个长度为 $3$ 的公共子序列是 $(1, 2, 5)$。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示排列的长度。

每个测试用例的第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$，所有 $p_i$ 互不相同)，表示该排列的元素。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出 $n$ 个整数 $q_1, q_2, \dots, q_n$ ($1 \le q_i \le n$，所有 $q_i$ 互不相同)，即 $1$ 到 $n$ 的任意一个排列，使得 $LCS((q_1, q_2, \dots, q_n), (p_{q_1}, p_{q_2}, \dots, p_{q_n}))$ 的值最大。

样例

输入 1

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

输出 1

1 2 3 4
1 6 2 5 3 4

说明

在第一个测试用例中，对于 $q = (1, 2, 3, 4)$，我们有 $LCS((1, 2, 3, 4), (p_1, p_2, p_3, p_4)) = LCS((1, 2, 3, 4), (1, 2, 3, 4)) = 4$。

在第二个测试用例中，对于 $q = (1, 6, 2, 5, 3, 4)$，我们有： $LCS((1, 6, 2, 5, 3, 4), (p_1, p_6, p_2, p_5, p_3, p_4)) = LCS((1, 6, 2, 5, 3, 4), (6, 1, 5, 2, 4, 3)) = 3$；其中一个长度为 $3$ 的公共子序列是 $(1, 2, 3)$。