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
sys.setrecursionlimit(10000)
# default is 1000 in python


t = int(input())
# t = 1

for _ in range(t):
	n = int(input())

	if n ==1:
		print("FastestFinger")
	elif n ==2:
		print("Ashishgup")
	elif n % 2 != 0:
		print("Ashishgup")
	else:
		# find odd divs
		odd_divs = []
		even_div = []
		even_divs = 0
		for i in range(2,int(n**0.5)+2):
			if n % i == 0: 
				if i % 2 != 0:
					odd_divs.append(i)
				else:
					even_div.append(i)
					if (i // 2) % 2 == 0:
						even_divs += 1
		new_odd = odd_divs.copy()
		for i in odd_divs + even_div:
			if (n//i) % 2 != 0:
				new_odd.append(n//i)
			elif ((n//i) // 2) % 2 == 0:
				even_divs += 1 

		new_odd = list(dict.fromkeys(new_odd))
		if len(new_odd) > 0:
			if len(new_odd) > 1:
				print("Ashishgup")
			else:
				yes = 0
				for i in new_odd:
					if (n // i) % i == 0:
						yes = 1
				if yes == 1 or even_divs > 0:
					print("Ashishgup")
				else:
					print("FastestFinger")
		else:
			print("FastestFinger")


# try:
	# raise Exception
# except:
	# print("-1")
	

# thenos.sort(key=lambda x: x[2], reverse=True)

# int(math.log(max(numbers)+1,2))

# 2**3 (power)

# a,t = (list(x) for x in zip(*sorted(zip(a, t))))

# to copy lists use .copy()

# pow(p, si, 1000000007) for modular exponentiation

# my_dict.pop('key', None)
# This will return my_dict[key] if key exists in the dictionary, and None otherwise.



# bin(int('010101', 2))