human
Write me 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.
Using python3 can you solve the prior task?
assistant
#Here is Python program to determine the winner of the game if both of them play optimally.

from sys import stdin, stdout
import math,sys
from itertools import permutations, combinations
from collections import defaultdict,deque,OrderedDict
from os import path
import bisect as bi
import heapq 
def yes():print('YES')
def no():print('NO')
if (path.exists('input.txt')): 
    #------------------Sublime--------------------------------------#
    sys.stdin=open('input.txt','r');sys.stdout=open('output.txt','w');
    def I():return (int(input()))
    def In():return(map(int,input().split()))
else:
    #------------------PYPY FAst I/o--------------------------------#
    def I():return (int(stdin.readline()))
    def In():return(map(int,stdin.readline().split()))

def primeFactors(n): 
    odd=0
    eve=0
    
    # Print the number of two's that divide n 
    while n % 2 == 0: 
        eve+=1
        n = n //2
    # n must be odd at this point 
    # so a skip of 2 ( i = i + 2) can be used 
    for i in range(3,int(math.sqrt(n))+1,2): 
          
        # while i divides n , print i ad divide n 
        while n % i== 0: 
            if i&1==1:
                odd+=1
            else:
                eve+=1 
            n = n //i 
    
    # Condition if n is a prime 
    # number greater than 2 
    if n > 2: 
        if n&1==1:
            odd+=1
        else:
            eve+=1

    return [odd,eve] 

def main():
    try:
        n=I()
        #print(n)
        if n==1:
            print('FastestFinger')
        elif n==2:
            print('Ashishgup')
        elif n&1==1:
            print('Ashishgup')
        else:
            l=primeFactors(n)
            win='-1'
            if l[0]==0 and l[1]==1:
                win='A'
            elif l[0]==0 and l[1]>1:
                win='F'
            elif l[0]==1 and l[1]==1:
                win='F'
            elif l[0]==1 and l[1]>=1:
                win='A'
            elif l[0]>=1 and l[1]==1:
                win='A'
            else:
                win='A'
            if win=='A':
                print('Ashishgup')
            else:
               ...