Walter 总说他所做的一切都是为了家人。但实际上，由于虚荣心作祟，他变得沉迷于尽可能多地赚钱。

事实证明，他的收入等于在所有从 $1$ 到 $n$ 的整数排列 $(q_1, q_2, \dots, q_n)$ 中，使得 $f((q_1, q_2, \dots, q_n)) + f((p_{q_1}, p_{q_2}, \dots, p_{q_n}))$ 取得的最大值。

这里 $p_1, p_2, \dots, p_n$ 是 Walt 最喜欢的排列，$f(a)$ 定义为满足 $a_i = \max(a_1, a_2, \dots, a_i)$ 的位置 $1 \le i \le n$ 的数量，换句话说，即前缀最大值的个数。

请找出一个从 $1$ 到 $n$ 的整数排列 $(q_1, q_2, \dots, q_n)$，使得 Walt 的收入最大化。如果存在多个这样的排列，输出其中任意一个即可。

输入格式

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

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)，表示 Walt 最喜欢的排列的长度。

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

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

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

样例

样例输入 1

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

样例输出 1

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

说明

在第一个测试用例中，对于 $q = (1, 2, 3)$，其值为 $f(1, 2, 3) + f(p_1, p_2, p_3) = f(1, 2, 3) + f(1, 2, 3) = 3 + 3 = 6$。

在第二个测试用例中，对于 $q = (1, 3, 4, 2)$，其值为 $f(1, 3, 4, 2) + f(p_1, p_3, p_4, p_2) = f(1, 3, 4, 2) + f(2, 3, 1, 4) = 3 + 3 = 6$。

在第三个测试用例中，对于 $q = (1, 3, 5, 4, 2)$，其值为 $f(1, 3, 5, 4, 2) + f(p_1, p_3, p_5, p_4, p_2) = f(1, 3, 5, 4, 2) + f(1, 2, 3, 4, 5) = 3 + 5 = 8$。