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 sys import stdin, stdout

class SOLVE:
    def sieve(self, prime):
        check = {}
        
        for i in range(3, 178, 2):
            if i not in check:
                for j in range(i*i, 31623, 2*i):
                    check[j] = 1
        
        for i in range(3, 31623, 2):
            if i not in check:
                prime.append(i)
                
    
    def solve(self):
        r = input
        w = stdout.write
        
        prime = []
        self.sieve(prime)
        
        name = ['Ashishgup', 'FastestFinger']
        ans  = []
        
        for i in range(int(input())):
            n = int(input())
            
            even_prime_cnt = odd_prime_cnt  = 0
            
            while not n%2:
                n //= 2
                even_prime_cnt += 1
            
            for i in prime:
                while not n%i:
                    n //= i
                    odd_prime_cnt += 1
                    
            if n > 1:
                odd_prime_cnt += 1
                    
            if even_prime_cnt == odd_prime_cnt == 0:
                ans += [name[1], '\n']
            elif even_prime_cnt == 0 and odd_prime_cnt > 0:
                ans += [name[0], '\n']
            elif even_prime_cnt == 1 and odd_prime_cnt == 0:
                ans += [name[0], '\n']
            elif even_prime_cnt > 1 and odd_prime_cnt == 0:
                ans += [name[1], '\n']
            elif even_prime_cnt == 1 and odd_prime_cnt == 1:
                ans += [name[1], '\n']
            else:
                ans += [name[0], '\n']
                
        w(''.join(ans))
        
def main():
    s = SOLVE()
    s.solve()
    
main()