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.
import random 
  
# modulo function to perform binary  
# exponentiation  
def modulo(base, exponent, mod):  
    x = 1;  
    y = base;  
    while (exponent > 0):  
        if (exponent % 2 == 1):  
            x = (x * y) % mod;  
  
        y = (y * y) % mod;  
        exponent = exponent // 2;  
  
    return x % mod;  
  
# To calculate Jacobian symbol of a 
# given number  
def calculateJacobian(a, n):  
  
    if (a == 0):  
        return 0;# (0/n) = 0  
  
    ans = 1;  
    if (a < 0):  
          
        # (a/n) = (-a/n)*(-1/n)  
        a = -a;  
        if (n % 4 == 3):  
          
            # (-1/n) = -1 if n = 3 (mod 4)  
            ans = -ans;  
  
    if (a == 1):  
        return ans; # (1/n) = 1  
  
    while (a):  
        if (a < 0): 
              
            # (a/n) = (-a/n)*(-1/n)  
            a = -a;  
            if (n % 4 == 3): 
                  
                # (-1/n) = -1 if n = 3 (mod 4)  
                ans = -ans;  
  
        while (a % 2 == 0):  
            a = a // 2;  
            if (n % 8 == 3 or n % 8 == 5):  
                ans = -ans;  
  
        # swap  
        a, n = n, a;  
  
        if (a % 4 == 3 and n % 4 == 3):  
            ans = -ans;  
        a = a % n;  
  
        if (a > n // 2):  
            a = a - n;  
  
    if (n == 1):  
        return ans;  
  
    return 0;  
  
# To perform the Solovay- Strassen  
# Primality Test  
def solovoyStrassen(p, iterations):  
  
    if (p < 2):  
        return False;  
    if (p != 2 and p % 2 == 0):  
        return False;  
  
    for i in range(iterations): 
          
        # Generate a random number a  
        a = random.randrange(p - 1) + 1;  
        jacobian = (p + calculateJacobian(a, p)) % p;  
        mod = modulo(a, (p - 1) / 2, p);  
  
        if (jacobian == 0 or mod != jacobian):  
            return False;  
  
    return True; 

n=int(input())
for i in range(n):
    a=int(input())
    if a==1:
        print("FastestFinger")
    elif a==2:
        print("Ashishgup")
    elif a%2==0 :
        
        if a%4!=0 and solovoyStrassen(a//2,10):
            print("FastestFinger")
        elif (a&(a-1)==0):
            print("FastestFinger")
        else:
            print("Ashishgup")
    else:
        print("Ashishgup")
        
        
    
