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.
from sys import stdin, stdout
def II(): return int(stdin.readline())
#def II(): return int(input())
oddprimes=[]

def ispowerof2(num):
    if((num & (num - 1)) == 0):
        return 1
    return 0
def SieveOfEratosthenes(n):
    global oddprimes
    prime = [True for i in range(n + 1)] 
    prime[0]= False
    prime[1]= False
    p=2
    while (p*p<= n):
        if (prime[p]==True): 
            for i in range(p*2,n+1,p): 
                prime[i] = False
        p += 1
    oddprimes=[p for p in range(3,n+1) if prime[p]]

def isPrime(oddn):
    global oddprimes
    for p in oddprimes:
        if oddn==p:
            return True
        elif oddn%p==0:
            return False #has two odd divisors
    return True    

SieveOfEratosthenes(31623)
t=II()
for _ in range(t):
    n=II()
    ff,ag=False,False
    if n==1:
        ff=True
    elif n==2:
        ag=True
    elif n%2==1: #odd number>1, divide by number and make FF lose
        ag=True
    elif ispowerof2(n)==1: #even number, power of 2, have to subtract 1
        ff=True
    elif n%4==0:
        #even number, not a power of 2, divided by product of all odd powers, and leave even number>=4
        ag=True
    elif isPrime(n//2): 
        #n//2 is an odd prime, p
        #Ashishgup divides by p, leaves 2 for FF, who removes 1 and wins
        #Ashishgup removes 1, and leave n-1 which is off, FF wins
        ff=True
    else: #divide by odd factor and leaves 2
        ag=True
    if ff:
        stdout.write("FastestFinger\n")
    else:
        stdout.write("Ashishgup\n")
        