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 collections import Counter
from functools import lru_cache

players = ["Ashishgup", "FastestFinger"]


def factors(n):
    # Returns all the divisors of n
    # For example for 36, returns:
    # [1, 2, 3, 4, 6, 9, 12, 18, 36]
    fhead = []
    ftail = []
    for x in range(1, int(n ** 0.5) + 1):
        if n % x == 0:
            fhead.append(x)
            if x * x != n:
                # This check is to not insert sqrt(n) twice in head and tail portion of the list
                ftail.append(n // x)
    return fhead + ftail[::-1]


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

    if N == 2:
        # If 2, subtract 1
        # Next player can't move
        who = solve(N - 1) ^ 1
        assert who == 0
        return 0

    if N % 2 == 1:
        # If odd, divide by N
        # Next player can't move
        who = solve(N // N) ^ 1
        assert who == 0
        return 0

    assert N % 2 == 0

    # Subtracting by 1 is a useless move since it will result in a odd which means we lose
    who = solve(N - 1) ^ 1
    assert who == 1

    # So try to divide

    pow2 = 1
    odd = N
    while odd % 2 == 0:
        odd //= 2
        pow2 *= 2
    assert odd * pow2 == N

    if odd == 1:
        # No odd divisors, you are forced to do the subtract 1 and lose
        who = solve(N - 1) ^ 1
        assert who == 1
        return 1
    else:
        divisors = factors(odd)
        if len(divisors) == 2:
            # If the odd divisor is a prime you only have one move
            # If the pow2 is 2, you lose, otherwise you win
            who = solve(N // odd) ^ 1
            assert pow2 == N // odd
            if pow2 == 2:
                assert who == 1
                return 1
            else:
                assert who == 0
                return 0
        else:
            # If the odd divisor isn't a prime you want to leave him with a 2 * oddPrime or a pow2 that isn't 2
            # Either way you win
            if pow2 == 2:
                who = solve(N // divisors[-2]) ^ 1
                assert who == 0
            else:
                who = solve(N // odd) ^ 1
                assert who == 0
            return 0


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])
