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.
# def find_divs(n):
#     i = 2
#     divs = list()
#     while n > 1:
#         if n % i == 0:
#             divs.append(i)
#             n //= i
#             i = 2
#             continue
#         else:
#             i += 1
#     return divs

# def find_divs(n):
#     i = 2
#     even_d = list()
#     odd_d = list()
#     while n > 1:
#         if n % i == 0:
#             if i % 2 == 0:
#                 even_d.append(i)
#             else:
#                 odd_d.append(i)
#                 if len(odd_d) > 1:
#                     return even_d, odd_d
#             n //= i
#             i = 2
#             continue
#         else:
#             i += 1
#     return even_d, odd_d

# def find_divs(n):
#     i = 2
#     even_d = list()
#     odd_d = list()
#     limit_n = n // 2
#     while n > 1:
#         if n % i == 0:
#             if i % 2 == 0:
#                 even_d.append(i)
#             else:
#                 odd_d.append(i)
#             n //= i
#             i = 2
#             if len(odd_d) > 1:
#                 return even_d, odd_d
#             if (len(even_d) > 1) and (len(odd_d) > 0):
#                 return even_d, odd_d
#             if (len(even_d) > 1) and (n%2 != 0):
#                 even_d, [n]
#             continue
#         else:
#             i += 1
#             if i > limit_n:
#                 break
#     return even_d, odd_d

def factorize(n):
    factors = list()
    for d in range(2, int(n**0.5)+1):
        while (n % d == 0):
            factors.append(d)
            n //= d
    if n > 1:
        factors.append(n)
    return factors


def find_divs(n):
    divs = factorize(n)
    even_d, odd_d = [i for i in divs if i%2==0], [i for i in divs if i%2!=0]
    return even_d, odd_d


t = int(input())
for _ in range(t):
    n = int(input())
    if n == 1:
        print("FastestFinger")
        continue
    if n == 2:
        print("Ashishgup")
        continue
    if (n % 2) != 0:
        print("Ashishgup")
        continue

    even_d, odd_d = find_divs(n)    
    if len(odd_d) == 0:
        print('FastestFinger')
    else:
        if len(even_d) + len(odd_d)-1 >= 2:
            print('Ashishgup')
        else:
            print('FastestFinger')