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 sys
input = sys.stdin.readline

############ ---- Input Functions ---- ############
def inp():
    return(int(input()))
def instr():
    return(str(input()))
def inlt():
    return(list(map(int,input().split())))
# def insr():
#     s = input()
#     return(list(map(int, list(s[:len(s) - 1]))))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))


from collections import Counter


def Factor(n):
    Ans = []
    d = 2
    while d * d <= n:
        if n % d == 0:
            Ans.append(d)
            n //= d
        else:
            d += 1
    if n > 1:
        Ans.append(n)
    return Ans


def main():
    t = inp()
    first = 'Ashishgup'
    second = 'FastestFinger'
    for _ in range(t):
        n = inp()
        if n == 1:
            print(second)
        elif n == 2:
            print(first)
        else:
            ans = Factor(n)
            odd = 0
            even = 0
            for i in ans:
                if i % 2 == 0:
                    even += 1
                else:
                    odd += 1
            # print(even, odd)
            if even == 0:
                print(first)
            elif odd == 0:
                print(second)
            elif odd == 1 and even == 1:
                print(second)
            else:
                print(first)

        # elif n % 2 == 1:
        #     print(first)
        # else:
        #     x = n
        #     odd_del = False
        #     while x > 1:
        #         if x % 2 == 1:
        #             odd_del = True
        #             break
        #         x /= 2
        #     if odd_del:
        #
        #         print(first)
        #     else:
        #         print(second)




if __name__ == '__main__':
    main()