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.
#CF-650 (DIV-3)

'''test=int(input())
for i in range(test):
    b=input()
    ans=""
    if len(b)==2:
        ans=b
    else:
        ans+=b[0]
        j=1
        while j<len(b)-1:
            ans+=b[j]
            j+=2
        ans+=b[-1]
    print(ans)
'''
'''test=int(input())
for i in range(test):
    n=int(input())
    arr=[int(i) for i in input().split()]
    type1=0
    type2=0
    for i in range(n):
        if i%2==0 and arr[i]%2==1:
            type1+=1
        elif i%2==1 and arr[i]%2==0:
            type2+=1
    if type1!=type2:
        print(-1)
    else:
        print(type1)'''


'''test=int(input())
for i in range(test):
    n,k=[int(i) for i in input().split()]
    binary=input()
    suff=[float("inf")]*(n)
    suff[-1]=0 if binary[-1]=="1" else float("inf")
    for j in range(len(binary)-2,-1,-1):
        if binary[j]=="1":
            suff[j]=0
        else:
            suff[j]=1+suff[j+1]
    last=-1
    ans=0
    for i in range(len(binary)):
        if binary[i]=="0":
            if last!=-1:
                if i-last>k and suff[i]>k:
                    ans+=1
                    last=i
            elif suff[i]>k:
                ans+=1
                last=i
        else:
            last=i
    print(ans)'''


'''test=int(input())
for i in range(test):
    import heapq
    s=input()
    m=int(input())
    arr=[int(i) for i in input().split()]
    s=sorted("".join([i for i in s]))
    heap=[]
    for i in range(m):
        heapq.heappush(heap,(arr[i],i))
    ans=[""]*(m)
    t=0
    while heap:
        a,b=heapq.heappop(heap)
        while True:
            sum_=0
            for i in range(m):
                if ans[i]!="":
                    sum_+=abs(b-i)
            if sum_==a:
                break
            else:
                t+=1
        ans[b]=s[t]
    print("".join(ans))'''

#CODEFORCES GLOBAL ROUND

'''test=int(input())
for i in range(test):
    a,b,n=[int(i) for i in input().split()]
    ans=0
    while a<=n and b<=n:
        if a>=b:
            b+=a
        else:
            a+=b
        ans+=1
    print(ans)'''

'''k=int(input())
item="codeforces"
print(item,end="")
printable=10**(3)
s="s"*(10**(3))
k-=1
while k>printable:
    print(s,end="")
    k-=printable
print("s"*(k))'''

# codeforces 651 DIV-2

'''test=int(input())
for i in range(test):
    n=int(input())
    l=1
    r=n
    ans=1
    while l<=r:
        mid=l+(r-l)//2
        if mid*2<=n:
            ans=mid
            l=mid+1
        else:
            r=mid-1
    print(ans) '''


test=int(input())
for i in range(test):
    n=int(input())
    if n==1:
        print("FastestFinger")
    elif n%2:
        print("Ashishgup")
    elif n==2:
        print("Ashishgup")
    elif n&(n-1)==0:
        print("FastestFinger")
    else:
        res=[]
        i=2
        while i**2<=n:
            cnt=0
            while n%i==0:
                n=n//i
                cnt+=1
            res.append((i,cnt))
            i+=1
            #print(i,n)
        if n>1:
            res.append((n,1))
        prime=0
        alpha=0
        for i in res:
            if i[0]!=2:
                prime+=i[1] 
            else:
                alpha=i[1]
        if alpha>1:
            print("Ashishgup")
        elif prime>=2:
            print("Ashishgup")
        else:
            print("FastestFinger")


                
        




