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
# sys.setrecursionlimit(10**6) 
input=sys.stdin.readline
t=int(input())
d={}
def bfs(n):
    z=int(n**0.5)
    temp=[]
    if(n==1):
        return
    if(n%2!=0):
        if(e.get(n,0)==1):
            o[1]=1
        if(o.get(n,0)==1):
            e[1]=1
        return 
    if(n%2==0):
        if(mark.get(n-1,0)==0):
            if(e.get(n,0)==1):
                o[n-1]=1
            if(o.get(n,0)==1):
                e[n-1]=1
            if(e.get(n-1,0)==1 and o.get(n-1,0)==1 ):
                mark[n-1]=1
            temp.append(n-1)
    for i in range(2,z+1):
        v=n//i
        # print(i,v)
        if(n%i==0 and i%2!=0):
           
            # print(n,i,e,o,z)
            if(mark.get(v,0)==0):
               
                if(e.get(n,0)==1):
                    o[v]=1
                    
                if(o.get(n,0)==1):
                    e[v]=1
                if(e.get(v,0)==1 and o.get(v,0)==1 ):
                    mark[v]=1
            

                temp.append(v)
        if(n%i==0 and v%2!=0):
           
            if(mark.get(i,0)==0):
                if(e.get(n,0)==1):
                    o[i]=1
                   
                if(o.get(n,0)==1):
                    e[i]=1
                 
                if(e.get(i,0)==1 and o.get(i,0)==1 ):
                    mark[i]=1
           
                temp.append(i)

            
        # print(n,i,e,o,z)
    # print("lol")
    for i in range(len(temp)):
        bfs(temp[i])



            


for t1 in range(t):
    n=int(input())
    e={}
    o={}
    mark={}
    e[n]=1
    if(n==1):
        print("FastestFinger")
    elif(n%2!=0 or n==2 ):
        print("Ashishgup")
    else:
        bfs(n)
        if(o.get(1,0)==1):
            print("Ashishgup")
        else:
            print("FastestFinger")

