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
# from collections import defaultdict, deque
import math

# import copy
# from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 998244353

def yn(bo):
    if bo:
        print("Ashishgup")
    else:
        print("FastestFinger")

def wari(n):
    res = []
    for i in range(2, 100000):
        if n % i == 0:
            # res.append(i)
            # res.append(n // i)
            while(True):

                res.append(i)
                n //= i
                if n % i != 0:
                    break

    if n != 1:        #
        res.append(n)
    return res

def solve():
    n = getN()
    if n == 1 or n == 4:
        yn(False)
        return
    elif n == 2 or n % 2 == 1:
        yn(True)
        return

    # 偶数
    else:
        res = wari(n)
        # print(res)
        ans = 0
        ni,san = 0, 0
        for re in res:
            if re % 2 == 0:
                ni += 1
            else:
                san += 1


        if ni == 1 and san < 2:
            yn(False)
            return
        elif san == 0:
            yn(False)
            return
        else:
            yn(True)



def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    main()
    # solve()