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.
"""
grundy = [0]*100
grundy[1] = 0
for i in range(2, 100):
    state = []
    state.append(grundy[i-1])
    for j in range(3, i+1, 2):
        if i%j==0:
            state.append(grundy[i//j])
    for j in range(10000):
        if not j in state:
            grundy[i] = j
            break
print(grundy)
print([idx for idx, x in enumerate(grundy) if x==0])

output
[0, 0, 1, 2, 0, 1, 0, 1, 0, 1, 0, 1, 2, 1, 0, 3, 0, 1, 2, 1, 2, 3, 0, 1, 2, 3, 0, 3, 1, 2, 3, 1, 0, 3, 0, 2, 1, 2, 0, 3, 1, 2, 3, 1, 2, 4, 0, 1, 2, 3, 2, 3, 1, 2, 3, 2, 1, 3, 0, 1, 3, 1, 0, 4, 0, 2, 3, 1, 2, 3, 2, 1, 3, 1, 0, 4, 1, 2, 3, 1, 2, 4, 0, 1, 3, 2, 0, 1, 2, 1, 4, 2, 1, 3, 0, 2, 1, 2, 3, 4]
[0, 1, 4, 6, 8, 10, 14, 16, 22, 26, 32, 34, 38, 46, 58, 62, 64, 74, 82, 86, 94]

1 = lose
odds except 1 = win
2^1 = win
2^(n+1) = lose
2 * odd(not 1, only one) = lose
2 * odd(two odds) = win
2^(n+1) * odd(not 1) = win
"""
import math
t = int(input())
player = 'Ashishgup', 'FastestFinger'

def chk(n):
    x = int(math.sqrt(n))
    for i in range(3, x+1, 2):
        if n%i==0: return True
    return False

for _ in range(t):
    n = int(input())
    if n == 1:
        print(player[1])
    elif n % 2 == 1 or n == 2:
        print(player[0])
    else:
        e = 0
        while n % 2 == 0:
            n //= 2;
            e += 1
        if n == 1:
            print(player[1])
        elif e == 1:
            if chk(n):
                print(player[0])
            else:
                print(player[1])
        else:
            print(player[0])
            

    