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 sys import stdin, exit
from math import sqrt
input = stdin.readline

def i(): return input()
def ii(): return int(input())
def iis(): return map(int, input().split())
def liis():	return list(map(int, input().split()))
def print_array(a): print(" ".join(map(str, a)))

ff = 'FastestFinger'
ashi = 'Ashishgup'

def prime_factors(n):
	prime = []
	while n%2 == 0:
		prime.append(2)
		n = n//2
	for i in range(3, int(sqrt(n))+1, 2):
		while n%i == 0:
			prime.append(i)
			n = n//i
	if n > 2:
		prime.append(n)
	return prime


t = ii()
for _ in range(t):
	n = ii()		
	first = False
	second = False
	if n == 1:
		first = True
	elif n%2 == 1:
		second = True
	elif n == 2:
		second = True
	else:
		primes = prime_factors(n)
		count = 0
		twos = 0
		for i in primes:
			if i%2 == 1:
				count += 1
			else:
				twos += 1
		if twos == 1 and count == 1:
			first = True
		elif count >= 1:
			second = True
		#elif count == 1 and len(primes)-1:
			
		else:
			first = True

		#print(primes)

	if first:
		print(ff)
	else:
		print(ashi)
