Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Permutation Game

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputTwo players are playing a game. They have a permutation of integers $$$1$$$, $$$2$$$, ..., $$$n$$$ (a permutation is an array where each element from $$$1$$$ to $$$n$$$ occurs exactly once). The permutation is not sorted in either ascending or descending order (i. e. the permutation does not have the form $$$[1, 2, \dots, n]$$$ or $$$[n, n-1, \dots, 1]$$$).

Initially, all elements of the permutation are colored red. The players take turns. On their turn, the player can do one of three actions:

- rearrange the elements of the permutation in such a way that all red elements keep their positions (note that blue elements can be swapped with each other, but it's not obligatory);
- change the color of one red element to blue;
- skip the turn.

The first player wins if the permutation is sorted in ascending order (i. e. it becomes $$$[1, 2, \dots, n]$$$). The second player wins if the permutation is sorted in descending order (i. e. it becomes $$$[n, n-1, \dots, 1]$$$). If the game lasts for $$$100^{500}$$$ turns and nobody wins, it ends in a draw.

Your task is to determine the result of the game if both players play optimally.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 5 \cdot 10^5$$$) — the size of the permutation.

The second line contains $$$n$$$ integers $$$p_1, p_2, \dots, p_n$$$ — the permutation itself. The permutation $$$p$$$ is not sorted in either ascending or descending order.

The sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case, print First if the first player wins, Second if the second player wins, and Tie if the result is a draw.

Example

Input

441 2 4 332 3 153 4 5 2 161 5 6 3 2 4

Output

First Tie Second Tie

Note

Let's show how the first player wins in the first example.

They should color the elements $$$3$$$ and $$$4$$$ blue during their first two turns, and then they can reorder the blue elements in such a way that the permutation becomes $$$[1, 2, 3, 4]$$$. The second player can neither interfere with this strategy nor win faster.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/08/2023 19:13:01 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|