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 sys
# Python program to print prime factors 

import math 

# A function to print all prime factors of 
# a given number n 
def primeFactors(n): 
       l=[]
       while n % 2 == 0:
           l.append(2)
           n = n / 2
       for i in range(3,int(math.sqrt(n))+1,2): 
          while n % i== 0:
              l.append(i)
              n = n / i
       if n > 2:
           l.append(n)
       return l
# Python program to check if given 
# number is power of 2 or not 

# Function to check if x is power of 2 
def isPowerOfTwo(n): 
	if (n == 0): 
		return False
	while (n != 1): 
			if (n % 2 != 0): 
				return False
			n = n // 2
			
	return True


# This code is contributed by Danish Raza 


# This code is contributed by Harshit Agrawal 


#This code is contributed by Gitanjali 

k=int(sys.stdin.readline())
for i in range(k):
    n=int(input())
    if (n%2!=0 and n!=1) or n==2:
        print("Ashishgup")
        continue
    
    if isPowerOfTwo(n)==True or n==1:
        print("FastestFinger")
        continue
    
    r=primeFactors(n)
    r=[int(i) for i in r]
    #print(r)
    f=r.count(2)
    if f>1:
        print("Ashishgup")
    elif f==1 and len(r)-f>1:
        print("Ashishgup")
    else:
        print("FastestFinger")

    
        
        
    
    
    
    
        
    
    
    
    
    
