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
import math as mt
input=sys.stdin.buffer.readline  
t=int(input())
def countDivisors(n) : 
      
    # Initialize count  
    # of divisors 
    count = 0
  
    # Note that this loop  
    # runs till square  
    # root 
    l=[]
    for i in range(1, (int)(mt.sqrt(n)) + 2) : 
        if (n % i == 0 ) : 
              
            # If divisors are 
            # equal, increment 
            # count by one 
            # Otherwise increment 
            # count by 2 
            if(( n // i == i )and i%2!=0 and i!=1) : 
                l.append(i)
                count = count + 1
            else : 
                if ((n//i)%2!=0  and (n//i)!=1):
                    l.append(n//i)
                    count+=1
                if(i%2!=0 and (i)!=1):
                    l.append(i)
                    count+=1
    #print(l)                
    return len(set(l))    
#t=1
def power(n):
    j=2
    p=1
    while 2*j<=n:
        j*=2
        p+=1
    return p    
        
for __ in range(t):
    #n,k=map(int,input().split())
    #l=list(map(int,input().split()))
    n=int(input())
    if n%2!=0 :
        if n==1:
            print("FastestFinger")
        else:
            print("Ashishgup")
    else:
        x=power(n)
        #print(x)
        if 2**x==n and x!=1:
            print("FastestFinger")
        else:    
            if n==2 or n%4==0:
                print("Ashishgup")
            else:
                x1=countDivisors(n)
                #print(111,x1)
                if x1>=2:
                    print("Ashishgup")
                else:    
                    print("FastestFinger")
                    