human
Can you provide a Python program to determine the winner of the game if both of them play optimally given the following:
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.
The above is tricky. Write me a correct solution in PYTHON.
assistant
#Here is Python program to determine the winner of the game if both of them play optimally.

"""
// Author : snape_here - Susanta Mukherjee
     
 """
 
from __future__ import division, print_function
 
import os,sys
from io import BytesIO, IOBase
 
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
 
 
def ii(): return int(input())
def fi(): return float(input())
def si(): return input()
def mi(): return map(int,input().split())
def li(): return list(mi())
 
 
def read():
    sys.stdin = open('input.txt', 'r')  
    sys.stdout = open('output.txt', 'w') 

def powerMod(x,y,p):
    res = 1
    x %= p
    while y > 0:
        if y&1:
            res = (res*x)%p
        y = y>>1
        x = (x*x)%p
    return res
 
def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

mod=1000000007

from math import *

import bisect

from decimal import *

getcontext().prec = 50

abc="abcdefghijklmnopqrstuvwxyz"

def fn(n):
    c=0
    while n%2==0:
        c+=1 
        n//=2 
    return c

def div(n):
    c=0
    for i in range(1,int(sqrt(n))+1):
        if n%i==0:
            if i!=n//i:
                if i>1 and i%2:
                    c+=1 
                if n//i>1 and (n//i)%2:
                    c+=1
            else:
                if i>1 and i%2:
                    c+=1 
    return c

pi=3.141592653589793238

def main():

    for _ in range(ii()):
        n=ii()
        if n==1:
            print("FastestFinger")
            continue
        if n==2:
            print("Ashishgup")
            continue
        if n%2:
            print("Ashishgup")
            continue 
        c=div(n)
        #print(c)
        if c==0:
            print("FastestFinger")
            continue
        if c>=2:
            print("Ashishgup")
            continue
        d=fn(n)
        #print(d)
        if d==1:
            print("FastestFinger")
        else:
            print("Ashishgup")

# region fastio
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd =...