Alice 是一位魔术师，她创造了一个新戏法。她有 $n$ 张牌，上面写着从 $1$ 到 $n$ 的不同数字。首先，她请观众洗牌并将牌排成一行。设从左往右第 $i$ 张牌上的数字为 $a_i$。

然后，Alice 选择两个排列 $p$ 和 $q$。$p$ 和 $q$ 必须满足一个限制条件——排列不能有不动点。这意味着对于所有 $i$ 都有 $p_i \neq i$ 且 $q_i \neq i$。

在选定排列后，Alice 根据这两个排列对牌进行洗牌。现在，从左往右第 $i$ 张牌变成了 $a_{p_{q_i}}$。如果洗牌后从左往右第 $i$ 张牌上的数字为 $i$，则戏法成功。

请帮助 Alice 选择排列 $p$ 和 $q$，或者指出对于给定的初始排列 $a$，不存在这样的排列。

输入格式

第一行包含测试用例的数量 $t$ ($1 \le t \le 10^5$)。

每个测试用例由两行描述。第一行包含一个整数 $n$ —— 牌的数量 ($1 \le n \le 10^5$)。第二行包含 $n$ 个整数 $a_i$ —— 牌的初始排列 ($1 \le a_i \le n$; $\forall i \neq j : a_i \neq a_j$)。

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

输出格式

按输入顺序为每个测试用例打印答案。

对于每个测试用例，如果不存在解，则在单独的一行中打印 “Impossible”。

否则，在第一行打印 “Possible”，并在接下来的两行中分别打印排列 $p$ 和 $q$。

样例

样例输入 1

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

样例输出 1

Impossible
Possible
3 1 2
2 3 1
Possible
3 4 2 1
3 4 2 1
Possible
4 1 2 5 3
3 1 4 5 2