狐狸喜欢排列！狐狸想出了以下问题，并要求猫来解决。

给定一个偶数正整数 $n$，以及长度为 $n$ 的排列 $p$ 。

另一个长度为 $n$ 的排列 $q$ 的得分，是长度为 $n$ 的数组 $a$ 中的局部极大值的数量，其中对于所有的 $i$ $(1≤i≤n)$ 有 $a_i=p_i+q_i$ 成立。换句话说，$q$ 的得分是这样的 $i$ 的数量：使得 $1<i<n$ (注意严格不等式)，$a_i−1<a_i$ ，且 $a_i>a_i+1$ (再次注意严格不等式)。

对于给定的 $n$ 和 $p$ ，请找出获得最大得分的排列 $q$。如果存在多个这样的排列，请选择任意一个。

注：长度为 $n$ 的排列，是指由 $n$ 个介于 $1$ 到 $n$ 之间的不同整数，按任意顺序组成的一个数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是一个排列 ($2$ 在数组中出现两次)，$[1,3,4]$ 也不是一个排列 ($n=3$ 但数组中有 $4$)。

输入:

输入的第一行包含整数 $t$ $(1≤t≤10^4)$ ，表示测试用例数量。

测试用例的第一行是偶数整数 $n$ $(4 ≤ n ≤ 10^5,n$ 为偶数) ，表示排列 $p$ 的长度。

测试用例的第二行有 $n$ 个整数 $p_1,p_2,…,p_n (1≤p_i≤n)$ 。保证 p 是长度为 n 的一个排列。

保证所有测试用例中，$n$ 的总和不超过 $10^5$ 。

输出:

对于每个测试用例，输出一行，包含长度为 $n$ 的任意排列 (数组 $q$ )，使得在给定约束条件下 $q$ 能够最大化得分。

示例

输入:

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

输出:

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

注意

在第一个示例中，$a=[3,6,4,7]$ 。数组只有一个局部极大值 (在第二个位置)，因此所选排列 $q$ 的得分为 $1$ 。可以证明在约束条件下这个得分是最优的。

在最后一个示例中，得到的数组 $a=[6,6,12,7,14,7,14,6]$ 有 $3$ 个局部极大值，分别位于第三、第五和第七个位置。