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 collections import Counter
from collections import defaultdict
from collections import deque
import math
import heapq
import sys
import io, os

input = sys.stdin.readline
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import *

rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().strip().split()))
rls = lambda: list(map(str, input().split()))



def factors(n):
    l= []

    # List to store half of the divisors
    for i in range(1, int(math.sqrt(n) + 1)):

        if (n % i == 0):

            # Check if divisors are equal
            if (n / i == i):
                l.append(i)
                #print(i, end=" ")
            else:
                # Otherwise print both
                #print(i, end=" ")
                l.append(i)
                l.append(int(n / i))
    return l

def check(n):
    l= []
    mx=-1
    # List to store half of the divisors
    for i in range(1, int(math.sqrt(n) + 1)):

        if (n % i == 0):
            print(i,n//i)
            # Check if divisors are equal
                #print(i, end=" ")
            if((n//i)!=1 and (n//i)%2!=0 and (n//(n//i))%2==0):
                mx=max(mx,n//i)
            elif(i!=1 and i%2!=0 and (n//i)%2==0):
                mx=max(mx,i)
                # Otherwise print both
                #print(i, end=" ")
    return -1


# Python3 program to find prime factorization
# of a number n in O(Log n) time with
# precomputation allowed.
import math as mt

MAXN = 1000001

# stores smallest prime factor for
# every number
spf = [0 for i in range(MAXN)]


# Calculating SPF (Smallest Prime Factor)
# for every number till MAXN.
# Time Complexity : O(nloglogn)
def sieve():
    spf[1] = 1
    for i in range(2, MAXN):
        # marking smallest prime factor
        # for every number to be itself.
        spf[i] = i

        # separately marking spf for
    # every even number as 2
    for i in range(4, MAXN, 2):
        spf[i] = 2

    for i in range(3, mt.ceil(mt.sqrt(MAXN))):

        # checking if i is prime
        if (spf[i] == i):

            # marking SPF for all numbers
            # divisible by i
            for j in range(i * i, MAXN, i):

                # marking spf[j] if it is
                # not previously marked
                if (spf[j] == j):
                    spf[j] = i

                # A O(log n) function returning prime


# factorization by dividing by smallest
# prime factor at every step
def getFactorization(x):
    ret = list()
    while (x != 1):
        ret.append(spf[x])
        x = x // spf[x]

    return ret


# Driver code

# precalculating Smallest Prime Factor
#sieve()


# calling getFactorization function
def isPrime(n):
    # Corner cases
    if (n <= 1):
        return False
    if (n <= 3):
        return True

    # This is checked so that we can skip
    # middle five numbers in below loop
    if (n % 2 == 0 or n % 3 == 0):
        return False

    i = 5
    while (i * i <= n):
        if (n % i == 0 or n % (i + 2) == 0):
            return False
        i = i + 6

    return True


t=int(input())
for _ in range(0,t):
    n = int(input())
    if(n==1):
        print("FastestFinger")
        continue
    if(n==2):
        print("Ashishgup")
        continue
    if(n%2!=0):
        print("Ashishgup")
    else:
        c=0
        #x=getFactorization(n)
        odd=0
        even=0
        c=0
        while(1):
           if(n%2==0):
               even=even+1
               n=n//2
           else:
               break
        x=isPrime(n)
        if(x):
            odd=1
        else:
            odd=2
        if (n == 1):
            print("FastestFinger")
        elif (even > 1):
            print("Ashishgup")
        elif (odd == 1):
            print("FastestFinger")
        else:
            print("Ashishgup")



