两个玩家正在玩游戏。它们具有整数的排列 $$$1$$$、$$$2$$$、...、$$$n$$$(排列是一个数组,其中从 $$$1$$$ 到 $$$n$$$ 的每个元素恰好出现一次)。排列不按升序或降序排序(即排列不具有 $$$[1, 2, \dots, n]$$$ 或 $$$[n, n-1, \dots, 1]$$$ 的形式)。
最初,排列的所有元素都被涂成红色。玩家轮流进行。在轮到他们时,玩家可以执行以下三个操作之一:
- 重新排列排列的元素,使所有红色元素保持其位置(请注意,蓝色元素可以相互交换,但这不是强制性的);
- 将一个红色元素的颜色更改为蓝色;
- 跳过回合。
如果排列按升序排序(即变为 $$$[1, 2, \dots, n]$$$),则第一个玩家获胜。如果排列按降序排序(即变为 $$$[n, n-1, \dots, 1]$$$),则第二个玩家获胜。如果游戏持续 $$$100^{500}$$$ 回合且无人获胜,则以平局结束。
您的任务是确定双方玩家都发挥最佳状态时的游戏结果。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 5 \cdot 10^5$$$) — 排列的大小。
第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ — 排列本身。排列 $$$p$$$ 不按升序或降序排序。
所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,如果第一个玩家获胜,则打印 First;如果第二个玩家获胜,则打印 Second;如果结果是平局,则打印 Tie。
示例
输入 #1
4 4 1 2 4 3 3 2 3 1 5 3 4 5 2 1 6 1 5 6 3 2 4
输出 #1
First Tie Second Tie
注意
让我们展示第一个示例中第一个玩家如何获胜。
他们应该在前两轮将元素 $$$3$$$ 和 $$$4$$$ 着色为蓝色,然后他们可以重新排序蓝色元素,使排列变为 $$$[1, 2, 3, 4]$$$。第二个玩家既不能干扰这个策略,也不能更快地获胜。