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.

×
C. Number Game

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAshishgup and FastestFinger play a game.

They start with a number $$$n$$$ and play in turns. In each turn, a player can make any one of the following moves:

- Divide $$$n$$$ by any of its odd divisors greater than $$$1$$$.
- Subtract $$$1$$$ from $$$n$$$ if $$$n$$$ is greater than $$$1$$$.

Divisors of a number include the number itself.

The player who is unable to make a move loses the game.

Ashishgup moves first. Determine the winner of the game if both of them play optimally.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains a single integer — $$$n$$$ ($$$1 \leq n \leq 10^9$$$).

Output

For each test case, print "Ashishgup" if he wins, and "FastestFinger" otherwise (without quotes).

Example

Input

7 1 2 3 4 5 6 12

Output

FastestFinger Ashishgup Ashishgup FastestFinger Ashishgup FastestFinger Ashishgup

Note

In the first test case, $$$n = 1$$$, Ashishgup cannot make a move. He loses.

In the second test case, $$$n = 2$$$, Ashishgup subtracts $$$1$$$ on the first move. Now $$$n = 1$$$, FastestFinger cannot make a move, so he loses.

In the third test case, $$$n = 3$$$, Ashishgup divides by $$$3$$$ on the first move. Now $$$n = 1$$$, FastestFinger cannot make a move, so he loses.

In the last test case, $$$n = 12$$$, Ashishgup divides it by $$$3$$$. Now $$$n = 4$$$, FastestFinger is forced to subtract $$$1$$$, and Ashishgup gets $$$3$$$, so he wins by dividing it by $$$3$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/22/2021 04:10:19 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|