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,math,cmath,time,bisect
from collections import deque 
start_time = time.time()
tt = 0
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
 
def solve():
    n = inp()
    if n==1:
        print("FastestFinger")
        return
    if n==2:
        print("Ashishgup")
        return
    if n%2==1:
        print("Ashishgup")
        return

    x=n
    cnt =0
    two=0
    while n>0:
        if n%2==0:
            two+=1
            n=n//2
        else:
            break
 
   
    if two ==1: 
        for i in range(2,int(math.sqrt(n)+1),1):
            
            if n%i==0:
                while n%i==0:
                    
                    n= n//i
                    cnt+=1
        
        if n>1:
            cnt+=1
        # print(cnt,n)
        if cnt == 1:
            print("FastestFinger")
            return
        print("Ashishgup")
    else:
        if n==1:
            print("FastestFinger")
        else:
            print("Ashishgup")
    




    
 
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
def main():
    
 
    t = 1
    t = inp()
    for tt in range(t):
        solve()
   
    # Comment these two lines 
    # print("Time Elapsed :",time.time() - start_time,"seconds")
    # sys.stdout.close()
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)
 
def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
    return(q)
# ONLINE_JUDGE = __debug__
# if ONLINE_JUDGE:
#     input = sys.stdin.readline
    
if __name__ == '__main__':
    main()