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 math import sqrt
divisor_dict = {}
def mrange(start, stop, step):
    while start < stop:
        yield start
        start += step

def is_prime(num):
    if num == 2:
        return True
    if (num < 2) or (num % 2 == 0):
        return False
    return all(num % i for i in mrange(3, int(sqrt(num)) + 1, 2))
def find_odd_divisor(n):
    odd_divisor = []
    odd_divisor.append(n)
    for i in range(2, int(n**(1/2))+1):
        if n%i == 0:
            odd_divisor.append(int(i))
            odd_divisor.append(int(n//i))
    # print(odd_divisor)
    odd_divisor = [i for i in odd_divisor if i%2!=0]
    divisor_dict[n] = odd_divisor

def find_winner(n):
    current_player = 'Ashishgup'
    next_player = 'FastestFinger'
    while(True):
        if n == 1:
            return next_player
        if n == 2:
            return current_player
        if n%2 != 0:
            return current_player
        if not n in divisor_dict:
            find_odd_divisor(n)
        if n%2 == 0:
            if len(divisor_dict[n])>0:
                if n%4 == 0:
                    return current_player
                else:
                    x = n/2
                    if(is_prime(x)):
                        return next_player
                    else:
                        return current_player
                    
            else:
                return next_player
        # if len(divisor_dict[n])>0:
        #     if n%2 == 0:
        #         return next_player
        #     else:
        #         n /= max(divisor_dict[n])
        # else:
        #     n -= 1
        # current_player, next_player = next_player, current_player

t = int(input())
t_input = []
for i in range(t):
    t_input.append(int(input()))
t_output = list(map(find_winner,t_input))

print(*t_output, sep='\n')
# print(divisor_dict[100])

