Ashishgup 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 ≤ t ≤ 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 ≤ n ≤ 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.
import io
import os

from functools import lru_cache
from collections import Counter, defaultdict, deque

players = ["Ashishgup", "FastestFinger"]
pow2 = [1]
for i in range(33):
    pow2.append(pow2[-1] * 2)
assert pow2[-1] > 10 ** 9
pow2 = set(pow2)


def primeFactors(n):
    # Returns a counter of prime factors of n
    # e.g., 12 returns {2: 2, 3: 1}
    assert n >= 1
    factors = Counter()
    while n % 2 == 0:
        factors[2] += 1
        n //= 2
    x = 3
    while x * x <= n:
        while n % x == 0:
            factors[x] += 1
            n //= x
        x += 2
    if n != 1:
        factors[n] += 1
    return factors


@lru_cache(maxsize=None)
def solve(N,):
    if N == 1:
        # first player can't move
        return 1

    if N == 2 or N % 2 == 1:
        # subtract 2 to 1
        # or divide by N
        # next player can't move
        return 0
    assert N % 2 == 0

    if N in pow2:
        # pow 2 case
        # no odd div, must subtract 1
        return solve(N - 1) ^ 1

    who = solve(N - 1) ^ 1
    if who == 0:
        return 0

    factors = primeFactors(N)
    oneOdd = None
    for k, v in factors.items():
        if k != 2:
            oneOdd = k
            break
    divs = [N // (2 ** factors[2])]
    if divs[0] != oneOdd:
        assert divs[0] % oneOdd == 0
        divs.append(divs[0] // oneOdd)
    for d in divs:
        if solve(N // d) ^ 1 == 0:
            return 0
    return 1


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    T = int(input())
    for t in range(T):
        (N,) = [int(x) for x in input().split()]
        ans = solve(N,)
        print(players[ans])
