题目描述

Have a nice day!

两个玩家在玩游戏。他们有一个由 $1,2,...,n$ 组成的排列（排列是指从 $1$ 到$n$ 的每个元素仅出现一次的数组）。 排列不按升序或降序排序（即 ：排列不具有形式 $[1,2,…,n]$ 或 $[n,n-1,…,1]$。 最初，排列的所有元素都是红色的。玩家轮流进行。轮到他们时，玩家可以做三个操作之一：

• 重新排一下排列的元素，使所有红色元素位置不变（注意，蓝色元素可以相互交换，但这不是必须的）；
• 将一个红色元素的颜色更改为蓝色；
• 跳过

如果排列按升序排序，则第一个玩家获胜（如：排列变成 $[1,2,…,n]$）,如果排列按降序排序，则第二个玩家获胜（如：排列变成 $[n,n-1,…,1]$）。如果游戏持续 $100^{500}$ 轮还没有人赢，那就评定为平局。 你的任务是确定游戏的结果（both players play optimally）。

输入格式

多组样例。第一行一个 $t(1 \leq t \leq 10^5)$，代表样例数。 每组样例包括两行。 第一行包含一个整数 $n(3 \leq n \leq 5 \cdot 10^5)$ 代表排列 的大小。 第二行 $n$ 个整数 $p_1,p_2,...,p_n$ ——排列自身。排列 $p$ 初始时既不降序也不升序。 保证所有样例的 $n$ 的总和不超过$5 \cdot 10^5$。

输出格式

对于每个测试用例，如果第一个玩家获胜，则输出 $First$ ，如果第二个玩家获胜则输出 $Second$ ，如果结果是平局，则输出 $Tie$ 。

样例

样例输入

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

样例输出

First
Tie
Second
Tie

提示

解释第一组样例，玩家一是如何获胜的： 他们应该在前两轮将元素 $3$ 和 $4$ 涂成蓝色，然后他们可以重新排列蓝色元素，使排列变为 $[1，2，3，4]$。第二个玩家既不能干扰这个策略，也不能更快地获胜。