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 collections import deque
from collections import OrderedDict
import math

from math import sqrt
from math import ceil

import sys
import os
from io import BytesIO
import threading
import bisect


import heapq

#sys.stdin = open("F:\PY\\test.txt", "r")
input = lambda: sys.stdin.readline().rstrip("\r\n")  

for t in range(int(input())):
    n = int(input())
    if n==1:
        print("FastestFinger")
        continue
    elif n==2:
        print("Ashishgup")
        continue
    elif n%2==1:
        print("Ashishgup")
        continue

    sqrN = int(ceil(sqrt(n)))
    cDiv = 0
    cDiv2 = 0
    while n%2==0:
        n/=2
        cDiv2+=1
    for i in range(3, (sqrN+1)):
        if i>n:
            break
        while n%i==0:
            n/=i
            cDiv+=1
    if n!=1:
        cDiv+=1
    if cDiv2==1:
         if cDiv==1:
             print("FastestFinger")
         else:
            print("Ashishgup")
    else:
        if cDiv==0:
             print("FastestFinger")
        else:
            print("Ashishgup")
    
            