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.
production = True

import sys, math, collections

def input(input_format = 0, multi = 0):

    if multi > 0: return [input(input_format) for i in range(multi)]
    else:
        next_line = sys.stdin.readline()[:-1]

        if input_format >= 10:
            use_list = False
            input_format = int(str(input_format)[-1])
        else: use_list = True

        if input_format == 0: formatted_input = [next_line]
        elif input_format == 1: formatted_input = list(map(int, next_line.split()))
        elif input_format == 2: formatted_input = list(map(float, next_line.split()))
        elif input_format == 3: formatted_input = list(next_line)
        elif input_format == 4: formatted_input = (lambda x: [x[0], list(map(int, x[1:]))])(next_line.split())
        elif input_format == 5: formatted_input = (lambda x: [x[0], list(map(float, x[1:]))])(next_line.split())
        elif input_format == 6: formatted_input = next_line.split()
        else: formatted_input = [next_line]

        return formatted_input if use_list else formatted_input[0]


def out(output_line, output_format = 0, newline = True):

    formatted_output = ""

    if output_format == 0: formatted_output = str(output_line)
    elif output_format == 1: formatted_output = " ".join(map(str, output_line))
    elif output_format == 1: formatted_output = "\n".join(map(str, output_line))

    print(formatted_output, end = "\n" if newline else "")


def log(*args):
    if not production:
        print("$$$", end = "")
        print(*args)

enum = enumerate

#
#   >>>>>>>>>>>>>>> START OF SOLUTION <<<<<<<<<<<<<<
#

def y(n):
    
    c = 0
    b = set()

    for i in range(2, math.ceil(n ** 0.5) + 1):
        if not n % i:
            for j in [i, (n // i)]:
                if j % 2 and j not in b:
                    b.add(j)
                    c += 1
                    if not n % (j ** 2):
                        c += 1
    return c

def solve():

    for i in range(30):
        log(i, y(i))
    # log(y(15))

    n = input(11)

    w = ("FastestFinger", "Ashishgup")

    if n == 1:
        out(w[0])
    elif n == 2:
        out(w[1])
    elif n == 4:
        out(w[0])
    elif n % 2:
        out(w[1])
    else:
        if y(n) and (y(n) > 1 or not n % 4):
            out(w[1])
        else:
            out(w[0])




    return


for i in range(input(11)): solve()
# solve()

#
#   >>>>>>>>>>>>>>>> END OF SOLUTION <<<<<<<<<<<<<<<
#
