背景

爱丽丝是一位魔术师，她创造了一个新魔术。她有$n$张卡片，每张卡片上都写有从1到$n$的不同数字。首先，她让观众洗牌并将卡片按顺序排列成一排。假设从左到右第$i$张卡片上的数字是$a_i$。

然后，爱丽丝选择了两个排列$p$和$q$。这些排列有一个限制条件 —— 排列不能有固定点。这意味着对任意$i$，有$p_i \neq i$ 且$q_i \neq i$。

排列选定后，爱丽丝根据这些排列对卡片进行洗牌。此时，从左到右第$i$张卡片就是$a[p[q[i]]]$。如果洗牌后第$i$张卡片上的数字是$i$，则该魔术被视为成功。

帮助爱丽丝选择排列$p$和$q$，或判断对于给定的初始排列$a$是否无法实现成功的洗牌。

描述

输入

输入的第一行包含测试案例的数量$t$ $(1 \leq t \leq 10^5)$。

每个测试案例包含两行。第一行包含一个整数$n$，表示卡片的数量$(1 \leq n \leq 10^5)$。第二行包含$n$个整数$a_i$，表示卡片的初始排列 $(1 \leq a_i \leq n; \forall i \neq j : a_i \neq a_j)$。

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

输出

按输入顺序输出每个测试案例的答案。

对于每个测试案例，如果无解则在一行中输出"Impossible"。

否则，首先输出"Possible"。然后在接下来的两行中依次输出排列$p$和$q$。

示例

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

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