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, stdout
from collections import defaultdict
cin = stdin.readline
cout = stdout.write
mp = lambda: list(map(int, cin().split()))
#Ashishgup FastestFinger

def bfs(x):
	y = int(x**.5)
	qu = []
	
	for i in range(2, y+1):
		if not x%i and (i%2 or (x//i)%2):
			if not (x//i)%2:
				#if x//i in d:
				#	return [d[x//i]]
				#else:
				qu.append(x//i)
				level[x//i].append(level[x][0]+1)
			if not i%2:
				#if i in d:
				#	return [d[i]]
				#else:
				qu.append(i)
				level[i].append(level[x][0]+1)
	
	if not qu:
		d[x] = 0
		qu.append(x)
		level[x].append(level[x][0])
	
	return qu 

d = {1:0, 2:1, 4:0, 6:0, 8:0, 10:0, 12:1, 14:0, 16:0, 18:1, 20:1, 32:0, 34:0, 38:0, 36: 1, 40:1, 42:1}
pl = ['FastestFinger', 'Ashishgup']
t, = mp()

for _ in range(t):
	n, = mp()
	
	k = 0
	level = defaultdict(list)
	if n in d:
		cout(pl[d[n]] + '\n')
	elif n%2:
		#k ^= 1
		#n = 1
		cout('Ashishgup\n')
	
	else:
		l = [n]
		f = 0
		k = 0
		level[n].append(0)
		while len(l) > 0:
			#k ^= 1
			if l[0] in d:
				#print(k, l[0])
				if (not d[l[0]] and level[l[0]][0]%2) or (not level[l[0]][0]%2 and d[l[0]]):
					cout(pl[1] + '\n')
					d[n] = 1
					f = 1
					break
				level[l[0]].pop(0)
			else:
				l += bfs(l[0])
				level[l[0]].pop(0)
				#print(l)
				#k ^= 1
				#print(k)
			l.pop(0)
			#if l [-1] == 0 or l[-1] == 1:
			#	if k == 0:
			#		cout(pl[l[-1]]+' 2\n')
			#	else:
			#		cout(pl[l[-1]^1]+' 3\n')
			#	f = 1
			#	break
			#print(100, l)
			
			
			
		if f:
			while l:
				l.pop(0)
		else:
			cout(pl[0] + '\n')
			d[n] = 0	
				
			
			