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 java.io.*;
import java.util.*;

/*
 * To execute Java, please define "static void main" on a class
 * named Solution.
 *
 * If you need more classes, simply define them inline.
 */

public class NumberGame {
  private static int[] findOddEvenCount(int n){
    int evenPart = 0;
    while(n > 0 && n%2 == 0){
      evenPart++;
      n = n/2;
    }
    return new int[]{n,1<<evenPart};
  }
  
  private static String findWinner(int n){
    if(n==1) return "FastestFinger";
    else if(n==2) return "Ashishgup";
    else if(n%2 == 1) return "Ashishgup";
    
    // even and > 4
    int[] oddEven = findOddEvenCount(n);
    int evenPart = oddEven[1];
    if(evenPart == n){
      // no odd divisor, hence no choice left except deduct 1 letting other player win
      return "FastestFinger";
    } else if(evenPart >= 4){
      return "Ashishgup";
    } else {
      // if the odd number is prime A loses
      // else A wins
      int oddPart = oddEven[0];
      if(isPrime(oddPart)){
        return "FastestFinger";
      } else {
        return "Ashishgup";
      }
    }
  }
  
  static boolean isPrime(int n) 
    { 
        // Corner cases 
        if (n <= 1) return false; 
        if (n <= 3) return true; 
      
        // This is checked so that we can skip  
        // middle five numbers in below loop 
        if (n % 2 == 0 || n % 3 == 0) return false; 
      
        for (int i = 5; i * i <= n; i = i + 6) 
            if (n % i == 0 || n % (i + 2) == 0) 
            return false; 
      
        return true; 
    } 
  public static void main(String[] args) {
    //int[] arr = findOddEvenCount(210);
    //System.out.println(Arrays.toString(arr));
    Scanner sc = new Scanner(System.in);
    
    int tests = sc.nextInt();
    
    while(tests > 0 ){
      int n = sc.nextInt();
      System.out.println(findWinner(n));
      tests--;
    }
  }
}


/* 
Your previous Plain Text content is preserved below:

1 -> lose
2 -> win
odd -> win
4 -> lose (0 odd divisor)
6 -> lose (1 odd divisor)
8 -> lose (0 odd divisor)
even ( odd * even ) - if even == 2 , lose else win

30 

15 2

90

45 2

3 3 5 2 

90 - A - 30 - F 10 A 2 F 

30 A 10 F 

number of odd divisors even or odd

30 A 10 F 2 A wins
30 A  6 F 2  A wins

90 A 30 F 10 A 5 2 F wins

3 5 2 

3 3 5 2 

90 

A 45 F wins
A 3 - 30 - 


3 * 5 = 15

15 * 7 = 105

3 5 7 11

23 

1 odd A loses

else 2 , 3 , 4 odd A wins
*/