在成为中国象棋冠军后，D 老师设计了一款名为“Tie-Tie”的双人游戏。

在 Tie-Tie 游戏中，有 $n$ 个编号从 $1$ 到 $n$ 的顶点。两条双向链 $L_1$ 和 $L_2$ 连接这 $n$ 个顶点。$L_1$ 的第 $i$ 条边连接节点 $i$ 和 $i+1$ ($1 \le i \le n-1$)。$L_2$ 的第 $i$ 条边连接节点 $p_i$ 和 $p_{i+1}$ ($1 \le i \le n-1$)。

游戏中的两名玩家分别是小青鱼（Little Cyan Fish）和小青羽（Xiao Qing Yu）。游戏开始前，小青鱼必须选择一个起始节点 $A$，小青羽必须选择一个起始节点 $B$。之后，他们轮流行动，由小青鱼先手：

• 小青鱼可以选择原地不动，或者沿着 $L_1$ 的边移动到另一个顶点；
• 小青羽可以选择原地不动，或者沿着 $L_2$ 的边移动到另一个顶点。

如果在某个时刻，小青鱼和小青羽位于同一个顶点，则会发生“Tie-Tie”。小青羽非常喜欢 Tie-Tie，但小青鱼不喜欢。因此，小青羽会试图促成 Tie-Tie，而小青鱼会试图阻止它。两位玩家都足够聪明，能够采取游戏的最优策略。

D 老师也是 Tie-Tie 的粉丝。如果无论两位玩家选择什么初始节点，小青羽都有策略在有限步数内与小青鱼达成 Tie-Tie，那么 D 老师就会很高兴。请帮助 D 老师确定在所有可能的初始状态下是否都会发生 Tie-Tie。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试数据的组数。

对于每组测试数据，第一行包含一个正整数 $n$ ($2 \le n \le 4 \times 10^5$)。

下一行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$。保证 $p$ 是 $[1, n]$ 的一个排列。

保证所有测试数据的 $n$ 之和不超过 $4 \times 10^5$。

输出格式

对于每组测试数据，如果无论两位玩家选择什么初始节点，小青羽都有策略在有限步数内与小青鱼达成 Tie-Tie，则输出一行，包含单词 Yes。否则，输出一行，包含单词 No。

样例

样例输入 1

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

样例输出 1

Yes
Yes
No
No
Yes